352.1

いやらしいセット...。問題の難易度は低いのに、実装の難易度は高いという感じ。一発勝負向きではないですね...。

250

関数再帰でfibを定義するときに、fib(0)とfib(1)が呼ばれる回数をfib(n)について答えよ、という問題。

何も考えずに、各呼び出し回数をメモしておいて、DPするだけ。DPの式もfibの式に一致するので、初項が微妙に違うfib関数になる。

500

荷物の重さがfibの値のいずれかになる状況で、ナップサック問題を解け、という問題。

重たい順、価値のある順、の辞書順ソートをまずする。後は、大きいものから順に、探索を開始する。詰めるときには同じ重さなら価値のあるものからとして良いので、いくつ詰めるかを探索する。このとき、自分より軽いのは全部詰められる個数(ダメなら0)以上詰められる個数以下を探索してやると良い。int溢れが頻発するので注意が必要。

なぜこれでうまくいくかというと、重さの制約がfibなので、大きい方の何かを1個スキップすると、その次のグループでは1個、更に次のグループでは2個、といった感じにfibだけ個数に余裕ができ、荷物の大きさがランダムな場合の最悪ケースの2^50と比べると、明らかに小さい量になる。(この場合、1個スキップすると二つ後ろのグループ以降は全部入れられるようになる。)

1000

現在の速度をx軸方向およびy軸方向について、それぞれ高々1だけ変化させて良い状況で、盤面上を開始点から終了点まで移動したい。何ステップで移動できるか答えよ、という問題。

愚直にBFSするだけの問題。適当にやり過ぎるとMLEになったりTLEしたりするので注意が必要なだけ。座標は進行方向の向きに応じて、適当に定数倍してやれば整数のままで扱えるので、その辺りを工夫する必要がありそう。(最適化の余地は色々あるけれど、75分の中で実装し切るのは大変だと思う...。)