415.1

250とチャレンジのセット。

250

クレーンの積載量とコンテナの重さリストが与えられて、何分で移動が終わるか、という問題。各クレーンは一分に一個しか運べない。

自分が運べる中で一番重たい荷物を各クレーンに割り当てるというのを収束するまで繰り返す。収束したときに箱が残っていたら無理、そうでなければ時間を答える。

500

N個のものの値段と価値が与えられ、総価値を目的の量にするにはいくら必要か答えよ、という問題。(最初にいくつか持っているが、それは全部換金してから考えれば良いので気にしない。)

Nは高々32のため、全通り試すのは無理。半分ずつに分割して、結果をマージするようにしてみたが、それはそれでダメだった。

最小費用流の類か、最大流とバイナリサーチに変形できるような気が一瞬しているけれど、まだ検証していない。

1000

AとBからなるN文字の列に対して、禁止部分文字列が与えられる。指定された順番の文字列を答えよ、という問題。

禁止文字列は高々17文字なので、2^17通りの文字列について禁止かどうかを判定しておけば良い。後は、直前の16文字とAかBで禁止されていないなら次の文字を試して、という処理を2^16通りの直前の文字と残りの文字の長さをステートにしてメモ付きで計算すれば、すべての状態についてどれだけ存在するかが計算できる。これから、指定された順番のものを先頭から順番に数えればおしまい。

実装は終わってないけど、計算量的には問題なさそうな気がする。