Quiz https://atcoder.jp/contests/typical90/tasks/typical90_bb AC (7/12 20:00以降に見れます) https://atcoder.jp/contests/typical90/submissions/23306592 解法 ランクを0, 1, 2, ...の順に確定していく 確定中に参照した本はその時点で関係者全てのラ…
Quiz Deck（★2）https://atcoder.jp/contests/typical90/tasks/typical90_bi AC✅ https://atcoder.jp/contests/typical90/submissions/23305242 ランダムアクセスがO(N)である場合も解ける https://atcoder.jp/contests/typical90/submissions/23290052 注意…
Quiz 057 - Flip Flap（★6） AC https://atcoder.jp/contests/typical90/submissions/23287874 掃き出し法？ 適用すると、行列が上三角行列（ or 行階段行列?）になる（下記画像） けんちょんさんの記事 https://www.google.com/search?q=Gauss-Jordan+%E3%8…
マージテクとは？ mapやsetやvectorなど、2つのデータをマージするときに小さい方から大きい方にマージすることでマージのオーダーが減るテクのこと 大変なルート #ABC202 E通した。オイラーツアーではない悪手(?)解法。クエリ先読み&木の深さごとのカウント…
1次元 D-Leaping Tak https://atcoder.jp/contests/abc179/tasks/abc179_d 2次元 E-Queen on Grid https://atcoder.jp/contests/abc183/tasks/abc183_e
Quiz https://codeforces.com/contest/1525/problem/D AC https://codeforces.com/contest/1525/submission/116394091 327ms... 想定解 DP 別解の最小費用流 辺を張りすぎてコンテスト中はTLE止まり れたすさんが辺の張り方を工夫して通した その方法は以下…
Segment Tree Beats というデータ構造がある
Quiz https://atcoder.jp/contests/abc042/tasks/arc058_b AC https://atcoder.jp/contests/abc042/submissions/22539182 解説 NG領域を考慮しない場合の数を求める NG領域を通る領域の場合の数を引く ここでNG領域の数え方だが、下図のようにNG領域の角から…
Quiz https://atcoder.jp/contests/abc198/tasks/abc198_d AC https://atcoder.jp/contests/abc198/submissions/22449517 TLE https://atcoder.jp/contests/abc198/submissions/22449518 説明 下の関数f, f2を見てほしい。string sの各アルファベットを第2引…
Quiz https://atcoder.jp/contests/past202104-open/tasks/past202104_h AC https://atcoder.jp/contests/past202104-open/submissions/22367788 解説 editorialとは別の解法なので書いておく 買う缶切りの数をx軸としたコスト関数を考えると凸になっている…
Quiz https://atcoder.jp/contests/arc115/tasks/arc115_c AC https://atcoder.jp/contests/arc115/submissions/22316432 解説 editorialと違う別解でACしたので書いておく 答えを左から（添字１から）埋めていく 添字 i を素因数分解して約数一覧を得る（こ…
Quiz https://codeforces.com/contest/1515/problem/C AC https://codeforces.com/contest/1515/submission/114914965 Solution editorial's solution : add each element to lowest my solution : sort array and put it in order i%M void solve(){ ll N,M…
動機 trail, pathの違い、circuit, cycleの違いが曖昧で「オイラーパス」などという存在しない用語を発することがないようにまとめた 頂点に注目した時の用語が path, cycle 辺に注目した時の用語が trail, circuit なのでオイラー路 = Eulerian-Trail であ…
Quiz https://codeforces.com/contest/1512/problem/D AC https://codeforces.com/contest/1512/submission/113376076 解説 editorialと違う解法だったので書いておく Aの和はどれだろうか？ Bを昇順ソートして、Aの和はBの最後端か、その手前に限られる そ…
Quiz Polygon for the Angle https://codeforces.com/contest/1096/problem/C AC https://codeforces.com/contest/1096/submission/112024305 その他 こういう問題も出るのね 定義を言えるか 円周角とは 中心角とは 円周角の定理とは
Quiz A.Deadline https://codeforces.com/contest/1288/problem/A AC https://codeforces.com/contest/1288/submission/111996556 解法 x日を最適化に使った場合にかかる日数をf(x)とすると、ceil関数を除けば下に凸 整数の三分探索をしそうになるが、それは…
構築問題とは 条件を満たすもの（配列やグラフ）の一例を答えとして出力するもの constructiveと言われることも 具体例 Quiz C.Balance the Bits https://codeforces.com/contest/1504/problem/C AC https://codeforces.com/contest/1504/submission/1119352…
Quiz C.Basic Diplomacy https://codeforces.com/contest/1484/problem/C AC https://codeforces.com/contest/1484/submission/111858181 解説 1度、適当にM日分アサインする 条件を満たさない人（オーバーしてしまう人）がいるとすれば1人で、それをｆ君と…
Quiz https://codeforces.com/contest/1505/problem/A 解説 interactiveな問題。endlならflushされるが、\nだとflushされないのでずっと待ちが発生し、Idle状態になってしまう 普段は\nの方が速いのでそっちを使っているが、interactiveかつ入力行数が不明の…
Quiz https://codeforces.com/contest/1400/problem/A AC https://codeforces.com/contest/1400/submission/111639333 解法 editorialとは別の解法として、真ん中の文字をn個続けたものが答えです void solve(){ ll N;cin>>N; string s;cin>>s; char c = s[N…
とある問題 https://codeforces.com/contest/1469/problem/D のeditorialにて、問題のサイズが処理1回ごとにsqrtされる解法があった https://codeforces.com/blog/entry/86082 その場合のステップ数はO(log log N)になる より理解したい人へ What would caus…
環境 windows 10 wsl2 g++ --stackは使えなかった とある問題にてメモ化再帰したが大きい値の時に手元の環境ではRE。再帰関数の呼びすぎでスタックオーバーフローしていると思われる。提出してみると通る https://codeforces.com/contest/1498/submission/11…
1度は出会っておかないと解けなさそう。 Going Home https://codeforces.com/contest/1501/problem/C AC https://codeforces.com/contest/1501/submission/110695476 A - Equal Weight https://atcoder.jp/contests/jsc2019-final/tasks/jsc2019_final_a AC …
Quiz https://atcoder.jp/contests/dp/tasks/dp_m AC https://atcoder.jp/contests/dp/submissions/20794817 解説 累積和を使っている解法が多かったのですが、imosで解けたので書いておく dpテーブルの定義は dp[i][j] : i個目まで見て、j個配ったときの場…
Quiz C - Sqrt Inequality https://atcoder.jp/contests/panasonic2020/tasks/panasonic2020_c 誤差に厳しい。C++のlong doubleだと通らない。EPS足せばEPSの値によっては通る pythonのdecimalで殴ってみる AC https://atcoder.jp/contests/panasonic2020/su…
algo-logicさんのライブラリをお借りした https://algo-logic.info/bridge-lowlink/ 橋（と関節点）をO(N+M)で求められる(AC)ことを確認した 無向連結グラフにおいて、「取り除いたときにグラフ全体が非連結になるような辺」を橋と言います verify (AtCoder)…
背景 ABC-Dでlong longのオーバーフローチェックが必要でした(C++erの場合) 積のオーバーフローチェックは a > INF / b がおすすめ— tatyam (@tatyam_prime) February 20, 2021 同値 上記発言の背景には同値関係があり、snukeさんも解説放送で説明していた h…
Quiz https://codeforces.com/contest/1486/problem/D AC https://codeforces.com/contest/1486/submission/107889074 解説 editorialの通りですが、なんとなくKは小さい方が大きいmedianが見つかる気がして、長さKのみ調べればいい気がしますが、間違いです…
Quiz https://codeforces.com/contest/1485/problem/C AC https://codeforces.com/contest/1485/submission/107728292 解説 editorialかkoboshiさんの解説を読みましょう https://koboshi.growi.cloud/Contests/701 学び 条件A=B=kと置いて式変形していくこ…
Quiz https://codeforces.com/contest/1490/problem/G AC https://codeforces.com/contest/1490/submission/107711008 解説（というか感想） 何周かして、最後の1周のどこでxに到達できるかという2段階で考える 何周すればいいかは数学でO(1)で求まるが、（…
