482.1

あんまりいい問題セットだとは思えなかった。

250

整数配列から、一つおきに取る、残りから二つおきに取る、残りから三つおきに取る、を繰り返したときに最後に取ることになる値を答えよ、という問題。

愚直にシミュレーションするだけというひどい問題...。

実際にはステップ数がそんなに深くない(ステップ数が一定数を超えたら最後の値を取ればいい)ので、何ステップ目で取るかを先頭から順に求めていけば良い。ある値をNステップ目で取ったなら、Nより大きいステップ目で取る値がN+1個出てこないとNステップ目では取れない、ということが分かるので、後何個大きいステップで回収する値が出てくればいいのかというのを、小さいステップ数について覚えておけばいい。経験的にこのステップ数はかなり小さい値に集中するので、問題サイズがかなり大きくても十分。

500

ハノイの塔を最短手で解くときのあるステップ目の手順が、与えられた順番づけで何番目になるか答えよ、という問題。

最短手も与えられる順番も再帰的な手続きになっているので、その手続きを追いながら順番を計算していけばいいだけのはず。

1000

時間がなくて見てない。