501.1

ゲームバランスが最近悪い気がする。

250

見てない。

500

長さNの数列のうち、いくつかの要素が埋められた状態で与えられるので、最初のK個の平均値以下になるようにK+1番目の要素を選びつつ、連続する三つが狭義単調減少にならないような数列はいくつ存在するか答えよ、という問題。

単調減少した回数と、直前の値と、今までの合計値でDPやるだけ。微妙に枝を狩ると通る。

1000

左右の移動の回数に制限があり、前進しかできない状況で、盤面上にN個あるものを目的の価値になるまで回収する。最短の時間を求めよ、という問題。

左右に移動した回数と前進した回数で時間は決まるので、回収できる順番でソートしてやればDPできる。左右移動で回収できるものの場合、両端を全通り試す必要があるので、かなり大変なことになる。

左に行ってから右に戻る、という動作を許容しないように、回収すべきものがあるライン(N個)について、どこの位置から入って、どこの位置へ出るか、という風な動作だけにして、その動作でどれだけ回収できるかをメモしておいて、DPをすれば、前進回数、左右移動回数、横位置でDPになるので、後はこれを適当なデータ構造で管理すれば良さげ？