588.1

難易度バランスおかしい。

250

N個のものからできるだけたくさんのものを選びたい。選ぶコストはそれぞれのコストと、それぞれの間の移動コストで決まる。指定された範囲のコストで最大いくつ選べるか答えよ、という問題。

両端を全ペア選んで中身をコスト小さい順に、というのが想定解っぽい。何も考えずに位置でソートして、DPしても通るとは思うけれども。

450

ドアを開けるのに2種類の鍵が必要で、必要な鍵の種類ごとの個数が書いてある。一度使ったら壊れる鍵が3種類あって、3種類目の鍵は他の鍵の代用ができる。ドアを開くといくつか鍵がもらえる。このとき、手持ちの鍵の個数の最大値を答えよ、という問題。開けるドアが残ってても良い。

取り敢えず、どのドアを開いたか、で鍵の合計値は決まる。種類の分布が変わるだけ。代用可能な鍵はできるだけたくさん持ちたいので、他一方の鍵の個数を状態に入れて、最大化するDPをやる。途中経過で、全部の鍵の合計値をメモしておけば良い。

全探索に枝狩り入れたら通るんじゃないかと思っているのだけれど、どうなんだろう？代用不可能な鍵の個数が、両方とも少ない状態で探索をしたことがあるのなら、そこを探索する価値はない、という感じ。もちろん枝狩り損ねるとひどいことが起こるのだけれど、そんなにひどいケースはあんまりなさそうなイメージ。

1100

見てない。