642.1

問題が枯渇しているからつまらないのかも知れないけれど、今日のは出題者の悪意しか感じない。

250

N個のものを確率に従って抽選するという操作を延々と繰り返す。抽選結果に応じて、次の抽選までの時間が決まる。抽選を開始した時刻から経過した時刻が与えられるので、次の抽選までの時間の期待値を求めよ、という問題。

確率はDPやるだけ。基本どおりですね。

500

木がN本ある。特定の高さ以上の木を特定の高さにする機械がM個ある。木の成長具合と日数が与えられるので、最終的に木の高さの合計値の最小値を答えよ、という問題。

状態が多すぎるので、マッチングしてはダメ。のはずなのだけれど、問題サイズが中途半端なので、多分頑張れば持っているライブラリと言語によっては通る。最終日の状態とそれまでの成長具合を適当にソートしたりとかして、うまいこと最小化すれば良いらしい。でもこれだと応用きかないので、やっぱりフローで解いた方がいいような気がする。

800

見てない。