475.1

問題が長いセット。

300

長さNの盤面上にK個ランダムに置いてある状態で、大きさが2になるまで盤面を右端から一個ずつ削っていく。削る過程で上に乗っていないようにするために、すべてのものは左右に1マス必ず移動する。何かと重なったら消えるが、必ず右端からはいなくなり、かつはみ出さないような移動をする。このとき、最後に残る個数の期待値を答えよ、という問題。

どうやっても解けるけれど、要は左右に1マスしか動かないので、奇数番目のマスのものと偶数番目のマスのものはぶつからない。最終的に2マス残るので、奇数番目のマスにいたものと偶数番目のマスにいたものがそれぞれ残り得る。って考えると両方のパリティが答え。後は初期配置のパターンを考えるだけ。

600

ときどき半分になるけど、ある規則で増えていく数列のK番目を答えよという問題。値はでっかいので法をとる。

法をとると情報落ちするので、半分にする操作の分くらいは余分に情報持っておきましょうね、という教育的配慮の問題。要は最終的にはちゃんとした法をとるけど、途中は半分になる回数分だけ大きめの値で法をとればいいということ。longには入らないのでBigInteger使うけど、そうすると行列乗算とか使うといいんじゃないかなぁ、的問題。(あんま考えてない。)

900

900は後回し。