309.1

600

整数列を狭義単調増加になるように変形するときに、変形する値の量の最小値を求めよ、という問題に帰着。

狭義単調増加なのを広義単調増加にするために、i番目の要素からiだけ引いておく。後はDPで求める。i番目の要素を移動させるとき、移動する先は他の要素と一致するはずであることから、配列数だけ移動先の候補がある。移動先が決まったらi-1番目の要素の移動先の候補はそれにより制限されているはずなので、一番いいヤツを選べばいい。

1000

整数列が広義単調増加である状態を維持したまま、すべての要素を0にすることを考える。交互に操作を行って先手が自分の番で終了できるならば、そうなる最初の処理を答えよ、という問題。

状態を抽象化する値を求めて、それを適切に操作できるならうまくいくし、そうじゃなければダメ、という系統の類だとは思うけれど、その辺はよく知らない。