久しぶりの企画。やっぱ DP 解けへんの良くないということで。
今回は Atcoder の Educational DP Contest をやっていきます。
昔少しやったことあるけど、復習として。
A - Frog 1
【問題】1-indexed で長さ N の数列 h[i] があり、その上に駒がある。1 番目から N 番目まで駒を移動させる。駒は i 番目から i+1 または i+2 番目に移動でき、かかるコストは移動先を j 番目として abs(h[i] - h[j]) である。かかるコストの最小を求めよ。
【制約】N <= 1e5, h[i] <= 1e4.
【答え】dp[i] を i 番目まで移動させるときの最小コストとすれば遷移が容易に書ける。遷移 O(1) なので全体で O(N).
【メモ】まあこれは簡単だけど、基本は「前の結果利用」で、N 番目の最小がほしい → N-1 番目と N-2 番目までの最小がほしい → さかのぼって全部ほしい、という思考過程になっている。これくらいならこんな思考せずとも思考停止で書けるべきだけどね。
なお、すべて 0-indexed と思って処理した。最近 1-indexed とごっちゃになってよくバグる。ホントは柔軟にやればいいけんだけど、そこで頭を使えるほど余裕がない...
B - Frog 2
【問題】基本は A - Frog 1 と同じ。ただし駒は i+K 番目まで動かせる。
【制約】A に加え、K <= 100.
【答え】上と同じ方法で問題ない。遷移が O(K) になるので、全体で O(NK). 十分間に合う。
【メモ】昔やったときは「1e7オーダー無理じゃねやばくね」とか思ったが、2secなら普通に通る。というか今回はそんなに更新しないためもっと早く通る。普段でも 1e7 くらいなら割と大丈夫で、1e8とかだと定数が小さくないと危ないか。計算量が意外となんとかなるケースも多いので、まずは愚直にやる方法を考えるのがよさそう。
C - Vacation
【問題】長さ N の数列 a[i], b[i], c[i] がある。N 個選んで和を最大にしたい。ただし index が i の 3 つから 1 つずつ選ぶとし、隣り合う場所では同じ数列から選んではいけない。答えはいくつ？
【制約】N <= 1e5. a[i], b[i], c[i] <= 1e4.
【答え】dp[i][k] で、i 番目に 種類 k のものを取るときの最大とすると、遷移が書ける。計算量 O(N*種類数).
【メモ】「足し方の制約をクリアするために状態数を増やす」の図。「DP とは DAG の最短経路だ！」をイメージするとよい？今回は思考としても自然か。難しい問題だと、いったん状態数を増やして、遷移が同じものをまとめる、とかもある。こわいな～
なお、この辺はずっと「もらうDP」で書いてる。そっちの方が個人的にはわかりやすい。その弊害かもだが、今回は「数列は 1-indexed で、0 からスタート」とした、これが一番わかりやすいと思うけどどうなんだろう。
D - Knapsack 1
【問題】荷物が N 個あり、それぞれ重さ w[i] と価値 v[i] が定まっている。いくつか選んで、重さが W 以下になるようにしつつ価値を最大化したい。価値の最大は？
【制約】N <= 100. W <= 1e5. w[i] <= W. v[i] <= 1e9.
【答え】dp[i][we] で、i 番目までで重さ we にする方法のなかでの価値の最大値とすると、遷移が O(1) で書ける。O(NW).
【メモ】典型的なナップサック問題。状態を増やす観点だと、制約のために重さを管理したともいえるし、全探索からの最適化とみると、何を取ったかを管理しなくとも、以前の状態で現在の重さと価値の最大を管理すれば十分ともみれる。
なお今回は配るDPで書いたが、DPの範囲外の値を更新していまいWAを吐いた。気を付けようね！
E - Knapsack 2
【問題】上に同じ。制約のみ変わる。
【制約】N <= 100. W <= 1e9. w[i] <= W. v[i] <= 1e3.
【答え】上のだと O(NW) で、この制約だとだめ。しかし価値が小さいことに注目するとよい。具体的には dp[i][va] を i 番目までで価値 va にするための重さの最小値とする 。(価値を増やすには、価値をfixしたらなるだけ重さを小さくしたい！) そうすると、似たような遷移が書けてとける。なお最後は dp[N][va]<=W となる最大の va を答えとするとよい。計算量は、V を v[i] の sum として O(NV).
【メモ】これも典型的な言い換え。括弧でかいたお気持ちが大事。勝手に名付けた「オーバーキル DP」に似てる、というか判定問題に帰着させたのでたぶん一緒。
F - LCS
【問題】文字列 S,T が与えられるので、共通の部分列のうち最長のものをひとつ出力せよ。
【制約】長さ <= 3000.
【答え】DPをしたあと経路復元するとよい。まず最長の長さを求める。これは、dp[i][j] を S の [0, i), T の [0,j) についての最長の長さとすれば、遷移 O(1) できる。実際、S[i-1] == T[j-1] なら dp[i][j] = dp[i-1][j-1]+1 (絶対取る)、それ以外だと dp[i][j] = max(dp[i-1][j], dp[i][j-1]) とするとよい。
復元は、見ている DP の index を i, j として、S[i-1]==T[j-1] なら答えに追加して i--, t-- とし、それ以外だと dpの値が一致する方へ i-- か j-- するとよい。最後にできた文字列を反転して終了。
【メモ】典型的なDPからの経路復元。最初みたときはスゲーって思いました。ABCのマッチ棒とかもこれ。「具体的に出力せよ」なので一瞬ギョッとするけど、冷静にDPでできると見抜かないといけませんね。ちなみにこれ「辞書式最小を求めよ」だとどうするんでしょうね...
【追記】辞書式最小を求める問題について
辞書式最小は、前からなるだけ小さくとりたいので、まずDPを「[i,ls], [j,lt] での最長の長さ」ととっておく。そのうえで、「長さ t まで決めて t 文字目を i, j 番目に決めたとして、文字 c ができるかどうかは、i, j 番目以降でcが出てくるindex ti, tj を調べてdp[ti][tj]+t = LCSならばとれる」という感じで前から復元していける。事前に「i 文字目以降で文字 c が出てくる最初の場所」を持っておけば、全体でもO(N^2+N*(文字の種類数)) でできる。
ツイッターに投げたら教えていただけました。ありがたい。
G - Longest Path
【問題】DAGが与えられるので、最長のpathの長さを求めよ。
【制約】グラフはN頂点M辺で N,M <= 1e5.
【答え】dp[i] を「i 始点のpathのうち最長の長さ」とすると、dp[i] は i → j な j すべてについての dp[j]+1 の max である。メモ化再帰でできる。O(N+M).
【メモ】露骨にDAGだったけど、普通のDPとは違い処理を行う順番が明示できない。しかしこういう場合でもメモ化再帰なら問題なくできる。再帰恐怖症を克服しよう！
H - Grid 1
【問題】H*W のグリッドが与えられる。グリッドの各マス目は空か障害物がある。左上から右下までのマスを伝った最短経路のうち、障害物のないマスのみを用いたものは何通りあるか？mod 1e9+7 で求めよ。
【制約】H, W <= 1e3.
【答え】左上原点の座標を考え、dp[i][j] を (i,j) 終点の求める最短経路の個数とすると、遷移が足し算で容易に書ける。あと、障害物があるときは無条件で 0 通りとしておくとよい。
【メモ】算数のやりすぎで自明に思えるが、正確に議論すると上のような感じ。初期化に注意。遷移順は横→縦とくまなくひろえば問題なし。
I - coins
【問題】N 枚のコインを振る。各コインについて、表の出る確率 p[i] が与えられる。表の枚数の方が裏の枚数より多い確率を求めよ。
【制約】N は奇数で、N <= 3e3. p[i] は小数第2位までの小数、0 <= p[i] <= 1.
【答え】 dp[i][head] を、i 番目までのコインで head 枚表が出る確率とすると、遷移が容易に O(1) で書ける。
【メモ】確率DP. N^2まで大丈夫なことを意識し、表の枚数を管理すればよい。
J - Sushi
【問題】長さ N の非負整数列がある。「等確率で項を選び、値を 1 減らす。0 なら何もしない」というのを繰り返す。すべて 0 になるまでかかる回数の期待値を求めよ。
【制約】N <= 300. 1 <= a[i] <= 3.
【答え】すべての項を保持すれば、期待値は漸化式で求められる。問題はそのままだと状態数が多すぎることだが、実際には 1, 2, 3 の個数が同じ状態はすべて期待値が一緒なので、dp[i][j][k] を 1, 2, 3 がそれぞれ i, j, k 個あるときの期待値として遷移を書けばよい。遷移は O(1) なので全体で O(N^3) (ただし定数小さい) となる。
【メモ】期待値DP. 最初が全部 1 なら逆数和になる有名なやつ。「操作しない」ケースがあっても漸化式が立てられる。状態をまとめられるのも大事 。(今回はまとめるというかもともと全部同じだから無駄を省いただけというか。)
K - Stones
【問題】数 K と長さ N の数列 a[i] を使って二人でゲームをする。各人は交互に、「数列の中から一つ数字を選び、その数だけKから引く、負にはできない」というのを繰り返す。操作できなくなったら負け。最善を尽くせば先手後手どっちが勝つか？
【制約】N <= 100. K <= 1e5.
【答え】dp[st] を「数が st のとき先手が勝つか否か」とするとよい。遷移が O(N) で、全体で O(NK).
【メモ】ゲームの問題とは相性がいいね。今回は 1 つの山だったので単純だが、山がたくさんある場合は Grundy 値を求めるとよい。具体的には、1つの山については Gr[st] を「遷移先の数にないようなもののうち最小の非負整数」としておき、Gr のXOR を取って判定する (Nimに帰着)。
L - Deque
【問題】長さ N の数列を使って二人でゲームをする。各人は交互に、両端の数字のどちらかを選んで消していき、無くなるまでやる。V = (先手の選んだ値の和) - (後手の選んだ値の和) として、先手は V を最大化、後手は V を最小化したい。最善を尽くしたときの V の値は？
【制約】N <= 3e3. a[i] <= 1e9.
【答え】dp[l][r] で「区間 [l,r) から始めたときの答え」とすると遷移が簡単に O(1) で書ける。ただし先手後手がどっちかは意識すること。全体で O(N^2) (定数小さい).
【メモ】区間DP. なんとなく遷移順がだるかったのでメモ化再帰でやったが、幅を最初にfixすればよかった。個人的には、なんとなく区間DPは見えにくくて、なんか頭のいい方法とか考えがちだけど、思考停止で解けるときは思考停止でやりましょう。
M - Candies
【問題】数 K と長さ N の非負整数列 a[i] が与えられる。次を満たす数列 x[i] としてありうるものの個数を、mod 1e9+7 で求めよ：
・x[i] たちの和は K
・各 i について 0 <= x[i] <= a[i].
【制約】N <= 100. K <= 1e5. a[i] <= K.
【答え】dp[i][ca] を「 i 番目までで和 ca となる数列の個数」とする。このとき遷移は dp[i][ca] = sum_{max(0, ca-a[i]) <= x <= ca} dp[i-1][x] となる。このままだと遷移に O(K) かかり、合計 O(NK^2) で間に合わないが、累積和を使えば遷移が O(1) となり全体で O(NK) となって間に合う。具体的には sum[i][ca] を x in [0,ca) なる dp[i][x] の和としておき、dpと同時更新すればよい。
【メモ】管理の仕方はナップサックと似てる (自然だけど)。今回は遷移に時短テク (累積和) が使えるパターン。これもDPの問題でよく見るなぁ。今回みたいにある区間についての和をとるときはこのテクが使える。累積和でなくとも、遷移の式の変形により計算量を落とせることもある。計算量については、状態数と遷移で別個にを意識するといいかもね。
残りはまた今度！
