245.1

SRM

300

トランプのサブセットが与えられ、その中からN枚取り出すとき、一番多いスートの枚数の期待値を答えよ、という問題。


各パターンの確率をDPで求めて、N枚になる確率と、その時一番多いスートの枚数から期待値を計算すれば良い。

500

ダイヤル式のカギをある状態から目的の状態にするまでのステップ数を答えよ、という問題。1回の操作では、連続する高々3桁を同じ値ずつ前後高々3つだけ移動させることができる。


今の3桁と残りの桁数を状態としてダイクストラ。先頭の桁が一致しているときに、桁数をシフトして新しい状態を作るようにする辺りが面倒。

1000

高々3つの砂時計を使って、N分の間に計ることのできない時間を求めよ、という問題。計ることができるとは、ある砂時計を反転させてから、いずれかの砂時計の砂がなくなるまでの時間のこと。


DPでやるには時間もメモリも足りなさそう。(メモリについては古い部分を破棄することでどうにかなるかも。)