読者です 読者をやめる 読者になる 読者になる

るくすの日記 ~ Out_Of_Range ~

主にプログラミング関係

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回目なのに詰まってしまった...