Eまで。Dから難しい……。
コンテスト後のツイート
D A[i]をindex 0におきたいなら、A[i]-iになる。index jにおきたいなら、A[i]-i+jになる。つまり、A[i]-iが隣あっていないと隣接させられない。
— titia (@titia_til) September 21, 2026
E メモ化再帰したら通った。
F. MEX Replacement
苦労したけど自力AC。
答えを二分探索する。
MEX xを作りたいなら、[0,x-1]が全て1個（以上）必要。そのためには、[0,x-2]まで全て2個必要、と差がsaならpow(2,sa)倍の個数必要になっていく。
そして、余ったものは、0に変えて使うことができる。
これらを使うと、自分以下のそれぞれに必要な個数が何個か、というのを持って大きい方からシミュレーションしていく（それがあまりにも大きくなったらその時点でダメ）ことで、「あるxを作れるか？」という判定問題が解ける。
答えで二分探索して大きい数字から見ていけば解けそう、という大まかな方針が分かった後も実装に苦戦。なかなか難しい問題という気がした。
0 件のコメント:
コメントを投稿