頭がこんがらがる．．． 考え方 回答例 勘違いしたこと 考え方2次元座標で考えるのが大事．チョコと箱を(縦, 横)でソートしておく．チョコの大きい順に見ていき，なるべくギリギリ入る箱を削除して（使って）いけば良い（使った箱しか候補から削除できない．…

考え方 回答例 考え方$B(x)$の最高次か最低次から順番に決めていくことができる． （「$C(x)$の最高（低）次数＝$A(x)$の最高（低）次数×$B(x)$の最高（低）次数」であるため，一意に決まる）制約でゼロでないのは最高次なので，次数が高い順に決めていく．…

考え方 回答例 (Python) 回答例 (C++) 考え方最小値を最大にする問題なので，二分探索ぽい．実際， 答え$x$を決め打ちすれば，$K+1$個に分割できるかどうかは$O(N)$でシミュレーションでき（※）， ある値を堺に$K+1$分割できる / できなくなるが決まる とな…

考え方 回答例 考え方まずは，$X$を偶数回云々を抜きにした，一段簡単な問題を考える．再帰で全ての道順を試して，$K$個の辺を通ったらreturnする方針では間に合わない（$\pmod{998244353}$を要求されていることからもわかるように）．そこで「ある頂点に行…

考え方 回答例 考え方部分列の中含まれる「(1の数) - (0の数)」のパターンが何通りあるか，という問題．累積和のパターンが何通りあるかを考えれば良さそうだが，1の数が変化しても，0の数が変化しても累積和が変化してほしい．そこで，0を-1で置き換えて累…

考え方 回答例 考え方「$y-x$を大きい方から順に調べて，初めて$\gcd(x,y) = 1$となるものを出力すれば，制限時間内に止まるだろう」という方針でうまくいく．コンテスト中に計算量まで考えるのはなかなか大変． Editorial - AtCoder Regular Contest 137回…

考え方 回答例 (Python) 回答例 (C++) 考え方$N+1$回以内にループに入る．そこで，次のようにすれば良い． $N+1$回を上限にループして ループに入るスタート地点startを（アメの合計個数として）検知する． そのときの周期periodを覚えておく 1周期で増える…

考え方 回答例 (Python) 考え方条件を満たす文字列$X$が，初めから何文字目で$S$と異なるかで場合分けして数え上げる．$S$と$i$文字目で異なる回文$X (\leq S)$としてあり得るものの個数は，次の積で求められる． $i-1$文字目までは$S$と一致するので1通り $…

【関連】 C - Large RPS Tournament 考え方 回答例 (Python) 回答例 (C++) 参考 考え方倍々に増えていく．逆に，再帰をすれば半分になっていく．$k \leq 10^{18} = 1000^{6} \sim 2^{60}$だから，60回再起すれば $S^{(t)}[0]$に行き着く（$S^{(t)}[0]$は$t$…

Pythonが苦手とする順序付き集合の問題なので，C++で解けるようにする（順序付集合 - 競プロはじめました）． 考え方 回答例 考え方(C++) ABC217D - Cutting Woods - 競プロはじめましたと似ている．値に重複があるのが異なる．順序付き集合が使えれば，あと…

Python（ABC217D - Cutting Woods - 競プロはじめました）では非常に苦労したので，C++で解けるようなるためのメモ．Pythonに比べてメチャクチャ簡単に実装できる．【関連】順序付集合 - 競プロはじめました 考え方 回答例 考え方ソート状態を保ったままカッ…

Pythonで順序付き集合の処理をしようとして苦労することが多い．そこで，順序付集合はC++で解けるようにしておきたい．使うのは<set>．この中に，キーの重複を許さないsetと，キーの重複を許すmultisetがある．ソートを保ったまま，要素の挿入（insert）を対数時</set>…