248.1

DP大好きなセット？

250

入力文字列の先頭の文字を中央に置き、2文字目をその文字の上下左右に配置し、3文字目を2文字目の上下左右のうち何も置かれていない場所に置く。以下同様に繰り返していった結果できる配置の中央から、一番外側までの文字を上下左右の任意の方向に一文字ずつ追加していって、元の文字列と同じ文字列を得るのは何通りか答えよ、という問題。

パスカルの三角形の総和を計算していくだけ。入力文字列の長さが1のときに1になることを除けば、文字列長Nについて2^(N+1)-4という式になる。

500

N個のタスクをK個の会社に外注することを考える。i番目のタスクが終わらないとi+1番目のタスクが開始できない状況で、同じ会社に連続して3回外注することはできない。このとき最小のコストを求めよ、という問題。

直前二回どこに外注したかを覚えておいて、終わったタスク数とその時点での最小コストについてDPするだけ。

1000

バスケットボールの試合で、残り時間と得点確率などが与えられるので、片方のチームが勝つ確率を求めよ、という問題。

条件が色々あるけれど、残り時間と得点差とどっちのチームの攻撃中かでDPすれば終わる。