codeforces
Quiz https://codeforces.com/contest/1342/problem/C 解説 l～rの範囲で数えたい。0～xまでの範囲で数えることが f(x)でできるなら、f(r) - f(l-1)で求められる。よくあるテク 周期a x bで同じ結果となるので、f(0) ～ f(a x b)までを事前計算しておき、fを…
Quiz https://codeforces.com/contest/131/problem/D 閉路見つけてそこからの距離（下記画像はサンプル２） AC https://codeforces.com/contest/131/submission/74636017 解法 閉路が1つだけあることが決まっているので、dfsして再訪した点があれば、それは…
Quiz https://codeforces.com/contest/396/problem/C N頂点の木 (3 x 10^5) クエリQ (3 x 10^5) ・1 v x k : 頂点vにxを足す。vの子孫にも、vからの距離 i によりx - i kを足す ・2 v : 頂点vの値をmod 10^9+7でprint 足す値が一律ではないことをどう扱うか …
Quiz https://codeforces.com/contest/1111/problem/C AC Code https://codeforces.com/contest/1111/submission/56781314 解法 考えている範囲で一気に燃やすコスト 考えている範囲を二分割して個別に燃やすコスト 上記２つのうち、安い方を選ぶように再帰…
Quiz https://codeforces.com/contest/1114/problem/D AC Code https://codeforces.com/contest/1114/submission/56634318 LCSのvector versionがある 解説 1 2 3 4 5 を考えてみる この場合はどこから始めても、4回の塗りが必要。一般に、N-1回塗れば同色に…
Quiz https://codeforces.com/contest/1108/problem/E1 AC Code https://codeforces.com/contest/1108/submission/56534524 解法 制限が緩いので全探索 A[i]のそれぞれが最終的にmaxになる値だとする その時、iを含むsegmentを適用する理由はない なので、i…
Quiz https://codeforces.com/contest/1136/problem/D AC Code https://codeforces.com/contest/1136/submission/56483886 参考 https://cinnamo-coder.hatenablog.com/entry/2019/03/12/033934 ポイント 一番後ろ（私）が前の列の人を追い抜くのではなく、…
Quiz https://codeforces.com/contest/1061/problem/D AC Code https://codeforces.com/contest/1061/submission/56465574 解法 showの開始順にソート 空いているTVがあり、それを使った方が「新規に借りるよりも得」の場合は再利用する その時、空いているT…
Quiz https://codeforces.com/contest/1183/problem/E string sが与えられる K個の部分文字列を作るのに必要な最低コストを求めよ 部分文字列tを作るコストは、sから取り除いた文字数である AC Code https://codeforces.com/contest/1183/submission/5617960…
Quiz https://codeforces.com/contest/1180/problem/C AC Code https://codeforces.com/contest/1180/submission/55893151 観察 シミュレーションしてみる 一番大きい値が左端に来た後は、居座る その後は、左端以外で周期的になる a, mの範囲が広いので周期…
Quiz https://codeforces.com/contest/1180/problem/A AC Code https://codeforces.com/contest/1180/submission/55876143 解法 数列は1, 5, 13, 25, ... OEISに聞く https://oeis.org/search?q=1%2C+5%2C+13%2C+25&language=english&go=Search 計算量 O(1)
Quiz https://codeforces.com/contest/1182/problem/E Note Editorial https://codeforces.com/blog/entry/67614 天才かよ！？と思った点 cxを分解（分配）することでcx fxの形にできる 三項の積になるが、g(x, p)を導入して三項の和にする するとトリボナッ…
Quiz https://codeforces.com/contest/1176/problem/E 高々N/2個の頂点で点被覆せよ AC https://codeforces.com/contest/1176/submission/55399046 bfsで黒と白(0, 1)に塗っている 解法 グラフを2色に塗る（例えば白と黒とする） 現在見ているノードを白で塗…
Quiz https://codeforces.com/contest/1165/problem/D Submission https://codeforces.com/contest/1165/submission/54147350 解法 Codeforces Round #560 (Div. 3) お疲れ様でしたA:下x桁を見る y桁目は1 それ以外は0にするB:ソートして昇順に見る 次が使え…
Quiz https://codeforces.com/contest/1159/problem/B Submission https://codeforces.com/contest/1159/submission/54048500 実験 サンプル3を見る |i-j| = 3のとき、minは717 k x 3 <= 717 k <= 239 これは答えと一致する 解法 |i-j|を幅と呼ぶことにする …
Quiz https://codeforces.com/contest/1163/problem/B2 Submit https://codeforces.com/contest/1163/submission/54007477 問題設定 配列Aの前からx個を見て、その中の1つだけを除外して、他の値の頻度が同じなら、そのxはOK [2,2,1,1,5,4,4]なら5を除外すれ…
Quiz https://codeforces.com/contest/1163/problem/C2 Submit https://codeforces.com/contest/1163/submission/54005559 解法 2点から直線が求まるので、係数a, b, cで表現する この時、係数を定数倍すると一致するものに注意する (a, b, c) = (1, 2, 3), …
Quiz https://codeforces.com/contest/1162/problem/E Submission https://codeforces.com/contest/1162/submission/53797164 解法 まず、1つでも空にしてしまうと負けである 次のターンに相手がN/2個を空にしてきて、自分はN/2個取れないので負ける 1, 1, 1…
Quiz https://codeforces.com/contest/1162/problem/C Submission https://codeforces.com/contest/1162/submission/53758184 考察 値 i がguess値と同じ時、1度だけ(i-1, i+1に)「分裂」できるとする すでに分裂済みで、またguess値と当たった時「捕まる」…
Quiz https://codeforces.com/contest/1144/problem/F 内容 無向グラフが与えられる それを有向グラフにし、各パスの長さを2より小さくせよ できない場合は-1を返す Submit https://codeforces.com/contest/1144/submission/52118977 観察 自分に矢印が向い…
Quiz https://codeforces.com/contest/1138/problem/B Submit https://codeforces.com/contest/1138/submission/51062002 英語 最初は問題の意図がよく分からなかった 前半にピエロをX人 後半にアクロバットをX人 にする必要がある。他の人は別のサポート役…
Quiz https://codeforces.com/contest/1133/problem/D Submit https://codeforces.com/contest/1133/submission/50980508 Note b/aが一致するものの個数の最大値が答え a==0は別対応する 落とし穴 コンテスト中、test 37でWA doubleを使っていたが精度に疑い…
Quiz https://codeforces.com/contest/1132/problem/C Submit https://codeforces.com/contest/1132/submission/50862056 解法 除去する2人を全パターン試すとO(N3)となってしまう 除去する1人を固定する 残りq-1人で塗る。各箇所が何回塗られたかをカウント…
Quiz https://codeforces.com/contest/1130/problem/C Submit https://codeforces.com/contest/1130/submission/50620759 解法 高々1つのみ橋を作れる 始点から幅優先で歩ける領域を確認 終点からも同様 始点領域の全点と、終点領域の全点でトンネルを掘って…
Quiz https://codeforces.com/contest/1130/problem/B Submit https://codeforces.com/contest/1130/submission/50619986 反省点 Div 2で多くの人が解けているなら貪欲を疑えばよかった 解法 https://twitter.com/torus711/status/1099724979476676608 B: 2 …
Quiz https://codeforces.com/contest/1131/problem/F Submit https://codeforces.com/contest/1131/submission/50398023 Note 問題文の図の通り、union find木などで結合していく グループ毎にメンバー一覧を持っておく 結合した時、グループAとグループBの…
Quiz https://codeforces.com/contest/1118/problem/C Submit https://codeforces.com/contest/1118/submission/50243260 解法 Nが偶数のとき 各値のカウントが4の倍数なら解ける。対称に置くだけ Nが奇数の時 4個以上ある値を4隅に割り当てる 残りから十字(…
Quiz https://codeforces.com/contest/1118/problem/D1 https://codeforces.com/contest/1118/problem/D2 Submit https://codeforces.com/contest/1118/submission/50237247 解法 d日で解けるかを二分探索 カフェイン列は大きい順にソートしておき、各日の早…
Quiz https://codeforces.com/contest/1117/problem/C Submit https://codeforces.com/contest/1117/submission/50138888 解法 二分探索 日数を固定(daysとする)したとき、まず流され、そのあと移動する 流された後の位置とゴールのマンハッタン距離 <= days…
Quiz https://codeforces.com/contest/1107/problem/A Submit https://codeforces.com/contest/1107/submission/50076744 Note cfはテストケース全部見せてくれるっぽい コンテストが終了しているからだろう 感想 正しく英語が読めているかどうか、という壁…
