285.1

SRM初め。いかにしてDPの適用範囲を制限するか、という問題セットだった。(単純にDPやるとTLEするよ、という意味で。)

250

ある文字列を高々N行で表示するときに必要な幅の最小値を答えよ、という問題。空白のみ改行に変更することができる。

最後に改行にした空白と、いくつ改行したかについて、その時の最小幅を覚えておくDPをする。本当は幅を下から順に決めていって、その時に少なくとも何行必要かを計算する方が簡単だし、それが想定解のはず。

500

NxNの盤面のどこかにロボットがいて、コマンド列を高々50000回実行する。このとき盤面に出るか、停止するまでの実行コマンド数の期待値を求めよ、という問題。コマンド列は高々50文字を循環して使う。

取り敢えず最初のサイクルで落ちる可能性のある領域を求め、そこのすべてのスコアを入れる。各サイクルで移動する分だけずらした先のスコアが、一サイクル後の自分のスコアになる。後はDPでテーブルを埋めて、最後に平均値を出すだけ。

1000

整数列が与えられるので、K種類の数字を含むように+1ないし-1の処理を任意の要素に行うことを考えるとき、この処理が必要な最小回数を答えよ、という問題。

まず整数列をソートする。K種類の数字を作成する場合、下から順に割り当てれば良いので、各文字について、それを割り当てるかどうかを決定する。I番目の整数について、J種類割り当て終了済みで、Xが最後に割り当てた数字、というのをDPする。これだと割り当て可能な範囲の2乗の計算量になるが、実際には割り当ては高々整数列の要素数だけ移動すれば十分なので、要素数の2倍の2乗で良い。要素数をNとすれば、O(N^3*K)で終了する。出現する数の範囲をDとすると、メモリ使用量が(N*K*D)なので、O(N*K*D^2)を間に合わないようにするにはDは1000付近になるっぽい。