Dynamic Programming 演習

タイトルのまんまです。
TopCoder SRMの過去問から解法に「Dynamic Programming」が含まれている問題をレベルで昇順にソートして解いていきます。
該当するDiv2Medium全18問中15問解きました。(残り3問は、dpでふつう解かないだろうみたいな問題だったので別解法で解きました)

[Div2]

(SRM366)
500:ChangingSounds
dp[i][j] := i-1番目までのIntervalsでボリュームをjにできるかどうか
<漸化式>
if(0 <= j + cI[i] and j + cI[i] <= mL) add = true;
if(0 <= j - cI[i] and j - cI[i] <= mL) sub = true;
dp[i + 1][j] = (add and dp[i][j + cI[i]]) or (sub and dp[i][j - cI[i]]);
やるだけ

(SRM555)
555:CuttingBitString
dp[i] := S[0,i]に含まれる5の累乗の個数の最小値
<漸化式>
dp[i] = min(dp[j - 1] + (check(S[j,n]) == True));
前はbfsで解いてた(計算量危ない)

(SRM534)
500:EllysCheckers
dp[i] := i(ボート)で先手が勝てるかどうか
<漸化式>
dp[i] = dp[xビット目から横に1つ移動] | dp[xビット目から二つジャンプ]
メモ化探索にしたほうが計算量落ちる

(Member SRM501)
500:FoxPlayingGame
dpmx[i][j] : = aをi回、bをj回使った時のscoreの最大値
dpmn[i][j] : = aをi回、bをj回使った時のscoreの最小値
<漸化式>
dpmx[a + 1][b] = max(dpmx[a + 1][b],max(dpmx[a][b] + sA,dpmn[a][b] + sA));
dpmx[a][b + 1] = max(dpmx[a][b + 1],max(dpmx[a][b] * sB,dpmn[a][b] * sB));
dpmn[a + 1][b] = min(dpmn[a + 1][b],min(dpmx[a][b] + sA,dpmn[a][b] + sA));
dpmn[a][b + 1] = min(dpmn[a][b + 1],min(dpmx[a][b] * sB,dpmn[a][b] * sB));
負の掛け算があるので最大値と最小値でdpする

(SRM363)
500:HandsShaking
dp[i] := i人の時の握手の種類
<漸化式>
dp[i] = sum(j to i){dp[j - 1] * dp[n - j - 1]}
一組の握手によって分割された平面に存在する他の握手の組が部分最適解

(SRM311)
500:MatchNumbersEasy
dp[i][j] := 右からi - 1番目までのmatchから重みj以下になるように選んだときの数字の大きさの最大値
<漸化式>
dp[i + 1][j] = strMax(dp[i][j - k * matches[i]] + string(k,'0' + i),dp[i + 1][j])
greedyやったほうが簡単そう
計算量に余裕があったので配列の再利用はしていない

(SRM531)
600:NoRepeatPlaylist
dp[i][j] := プレイリストi - 1番目までで、j種類の曲を使ったときの条件を満たした順列の総数
<漸化式>
dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j] * (N - j)) % MOD;
dp[i + 1][j] = (dp[i + 1][j] + dp[i][j] * (j - M)) % MOD; (j > M)
漸化式思いつかなかった..orz こういう数え上げ系は苦手です。
包除原理でも解けるらしい。どちらにせよ結構難しいなあ。

(SRM352)
500:NumberofFiboCalls
one[i] := iの時の1の個数
zero[i] : = iの時の0の個数
<漸化式>
one[i] = one[i - 1] + one[i - 2];
zero[i] = zero[i - 1] + zero[i - 2];
問題文に答えが書いてあるよ(震え声)

(SRM527)
550:P8XGraphBuilder
dp[i] := i個の頂点で作ったグラフのスコアの最大値
<漸化式>
dp[i + j] = max(dp[i + j], dp[i] + scores[j] + (j-1)*lisc) ;
個人的には結構難しかった。
グラフ理論理解しないと...

(SRM547)
500:PillarsDivTwo
dp[i][j] := i番目の円柱をjの高さにしたときのi番目までの高さの合計の最大値
<漸化式>
dp[i][k] = max(dp[i][k],dp[i - 1][j] + (j - k) * (j - k) + w * w);
やるだけなのに時間かかりすぎた。

(SRM422)
500:PrimeSoccer
dp[i][j] := i - 1番目まででj回ゴールした時の確率
<漸化式>
dp[0][x + 1][g] += (1.0 - sA) * dp[0][x][g];
dp[1][x + 1][g] += (1.0 - sB) * dp[1][x][g];
dp[0][x + 1][g + 1] += sA * dp[0][x][g];
dp[1][x + 1][g + 1] += sB * dp[1][x][g];
確率dpやるだけ。こういう問題やってると数学したくなってくる。

(SRM340)
500:ProblemsToSolve
dp[i][j][k] := i - 1番目まで最大値j最小値kとなるように解いたときの問題数の最小値
<漸化式>
dp[i + 1][j][k] = min(dp[i][max(j,x)][min(k,y)] + 1);
頭の中では解けてるのにバグらせる事多いなぁ...

(SRM325)
500:RGBStreet
dp[i][j] := i - 1番の家をj色にしたときのコストの最小値
<漸化式>
dp[i + 1][0] = min(dp[i][1] + cost[i][1],dp[i][2] + cost[i][2]);
dp[i + 1][1] = min(dp[i][0] + cost[i][0],dp[i][2] + cost[i][2]);
dp[i + 1][2] = min(dp[i][1] + cost[i][1],dp[i][0] + cost[i][0]);
やるだけ

(SRM411)
600:SentenceDecomposition
dp[i] := i - 1番目まで作ったときのコストの最小値
<漸化式>
min(dp[n + words[i].size()] + C(substr(n,validWords[i].size()),words[i]));
やるだけなんだけどやっぱりバグる

(SRM558)
600:Stamp
dp[i][c] := 区間[i - K + 1,i]にc色を塗った時の色の個数の最小値
<漸化式>

解くの2回目なのに詰まってしまった...