Dynamic Programming 演習(2)

前回(動的計画法(Dynamic Programming)演習 - るくすの日記 ~ Out_Of_Range ~)の続き。

今回は該当するDiv2Hardのうち13問解きました。

[Div2]

(SRM354)
1000:UnsealTheSafe
dp[i][j] := i-1番目にjを押すようなパスワードの総数
<漸化式>
sum += dp[i - 1][keypad[ny][nx]];
dp[i][j] = sum;
1000とは思えない簡単さ

(SRM281)
900:BinarySearchable
最初dpの漸化式考えていたけが、よく考えるとどんな状態でも任意の要素が見つかるか否かは一意に定まるので貪欲でいける

(SRM197)
1100:QuickSums
dp[i][j] := 直前にi番目を選んで和がjの時のコストの最小値
<漸化式>
dp[i][j] = min(dp[i][j],dp[i + k][sum - numbers.substr(i,k)] + 1)
1100にしては簡単。といいつつ、dp書いたらバグったのでメモ化した。

(SRM554)
1000:TheBrickTowerHardDivTwo
dp[i][c1][c2][c3][c4][k] := i + 1段目の左上がc1右上がc2左下がc3右下がc4で、kペアが同色で隣接しているときのTowerの種類の総数
<漸化式>
same = (c1 == c2) + (c2 == c3) + (c3 == c4) + (c4 == c1) +
(c1 == d1) + (c2 == d2) + (c3 == d3) + (c4 == d4)
dp[y][c1][c2][c3][c4][k + same] += dp[y - 1][d1][d2][d3][d4][k];
方針は立っていたが、いざ実装するといろいろバグったので、結局カンニング...
もっとうまい状態の持たせ方があって　なるほどー　ってなった。

(SRM502)
1000:TheCowDivTwo
dp[i][j][k] := i番目までの牛からj匹を選んで和をNで割った余りがkとなる組み合わせの個数
<漸化式>
dp[i + 1][j][k] += dp[i][j-1][(k-i+N)%N];
これもカンニング。いろいろ試すことは重要だなぁ...
2連続カンニングはつらぽよである。

(SRM520)
1000:SRMSystemTestPhase
dp[i][j]:= i番目までのcoderで前の状態がjの時の順位表の総数
<漸化式>
dp[i + 1][j] = dp[i][j + ('Pass','Challenge','Fail')] (j < j + ('Pass','Challenge','Fail'))
簡単なのに、順位づけを間違えてバグらせてしまった。というか題意を勘違いしまくっていた。

(SRM313)
1000:ParallelProgramming
dp[i]:= i番目までのタスクをこなした時の消費時間の最小値
<漸化式>

ほとんど同じような問題を以前PKUで解いていた。トポロジカルソートするだけ。(と言いつつ、このアルゴリズム、ちゃんと自分で書いたことがないw)
自分、早くグラフ理論勉強するべき。

(SRM339)
1000:OnTime
dp[i][j]:= 現在地iで現在時刻jの時のコストの最小値
<漸化式>
dp[i][j] = min(dp[to][start + time_cost] + cost);
簡単なのに、またしても題意を読み間違えていた。
バスの出発時刻と自分の到着時刻が一致しているときは乗れないらしい。

(SRM263)
900:DequeSort
dp[i] := 区間[0,i]における作る必要のあるキューの最少数
<漸化式>
dp[i] := min(dp[j]) (j < i)
ソートした数列を作れば分割統治的に解けるなー　簡単じゃん(フラグ)
と思っていざメモ化書くとバグるし、部分列が作成できるか否かを探索のたびにやっていたので計算量も結構やばくなる。
結局1時間半くらい費やしてしまいましたw

(SRM413)
1000:InfiniteSequence
dp[i] := A[i]
<漸化式>
dp[i] = dp[i/p] + dp[i/q]
Div2Easyでも文句言われなさそうな難易度。なんだこれ。

(SRM178)
1000:BadSubstring
dp[i][j] := i文字で直線がjの時の文字の総数
<漸化式>
dp[i + 1][j] += dp[i][k]
一瞬trieかと思ってビビったが、やるだけだった。

(SRM387)
1000:MarblesRegroupingHard
dp[i][j] := i番目までで使用した状況j(ビットマスク)の時のコストの最小値
<漸化式>
dp[i + 1][j] = min(dp[i][j | (1 << c)] + cost[i][c])
やるだけ。3問前の失敗を活かせたので良かったです。
でもまたバグらせて、時間費やしましたorz

(SRM523)
1000:SmallBricks31
dp[i][j] := 下段のブロック列i(ビットマスク)と上段のブロック列j(ビットマスク)の時の積み方の総数
<漸化式>
dp[i][j] += dp[j][条件を満たしているブロック列]
方針はすぐたったが、条件を満たしているかを判定する関数をバグらせて四苦八苦。(そこかよw)
結局そこはカンニングしました。
良問だと思う。こういうの好き。

どうでもいいけどこういう絵好きですw

とりあえずdpはかなり慣れてきたし、hardでも解法の方針は結構すぐに立つようになってきた。
ただ、やるだけの実装箇所でバグったり、初項の値間違えたりとクズいミスが目立って勿体ない箇所が多かったり。

慣れるしかないかなぁ