608.1

個人的には嫌いだし面白くない作業問題だったけれど、それを時間内にきっちり終わらせることができなければ意味がない。

300

A個以上B個以下入った箱が並んでいる。全部でN個あると分かっているときに、K個以上確実に回収するために開けないといけない箱の最小個数を答えよ、という問題。

取り敢えず、Aが大きい順にソートして、回収してやるか、Bが小さい順に除外してやるか、で最終的な箱の個数が小さい方が最適。何も考えずにサブミットするのが正解っぽい。

600

有向グラフ上の長さLのパスは何通りあるか、オーダーで答えよ、という問題。

取り敢えず自分へ戻ってくるパスが複数通りあると、そこで指数爆発するので、それはそれで処理する。ループだけしかない場合は、開始位置ですべてが決まる。ループが二つある場合は、いつもう一方に移動するか、で決まる。ループを全部でN回まわるなら、N通りある。ループが三つある場合は、最初の移動をK回目にやるなら、次の移動はN-K通りなので、全部のKについて考えると、N^2通りくらい。という感じで、結局、ループを移動できる回数で決まる。なので、ループを一つの点に縮退させて、ループ間での遷移を辺にして、最長路でも求めてやれば終わる。

というような感じのをひたすら実装するだけ。

900

見てない。