DPが苦手なので、練習します。
過去DPの練習コンテストが2回開かれているので、その問題を解いて、DPへの理解を深めていきます。
まずはTypical DP Constestを解いていきます。
A
i番目に値jになるかを判定するには、i-1番目で値jになるかのリストがあればO(1)で判定できる。よってこれでDPするとよい。
値を変数にするのは、この程度だと思いつくけど、複雑になると分かりづらくなる。あくまで「判定のために何の管理が必要か」と、考察ベースでいきたい。
B
先手の和を先手は最大化したく、後手は最小化したい。Aの山のi番目以降、Bの山のj番目以降が残っているとき(これを(i,j)と書く)の最大は、(i+1,j)と(i,j+1)の様子を見ればよい(先手後手で対応は変わるけど)。よってこれでDPできる。二重帰納法のイメージ。
なお、局所的な貪欲戦略(でかい方を取る)だとうまくいかないことに注意。また、DPテーブルがあれば最善戦略を復元もできる。おいしい。
C
iラウンド目にj番が勝ち上がる確率は、i-1ラウンドに勝ち上がる人の確率のリストがあれば計算できる。なのでこれでDPできる。参加人数をNとすると愚直に計算してO(N^2 *logN)で、最大でもN=1024なのでこれで間に合う。
確率を求めるDPはあんまり得意ではない...こういう愚直にできるものくらいは確実に解きたいな。
D
これも確率。余りを保持してDPするのはDが大きいと足りない。実際には1から6までのみかけ算するで、ほとんどの余りは使わない。正確には2,3,5べきのかけ算のところだけ使う。なので「i個まで掛けて2がa個、3がb個、5がc個あるような確率」でDPするとよい。ただしDの素因数の個数を超えたものは無視する。
計算量はO(N*(logD)^3)で、Dはでかいけどこれで十分間に合う。
なお、今回は「配るDP」をすると簡単。配るか貰うかの選択は、フローチャート(というかDAG)を局所的に見ると分かりそう。
E
Nは大きすぎるのでstringで受け取る。N以下というのが分かりづらいが、「上からi番目までを見た数以下で各位の和がmod Dでjのもの」とすると計算できそう。基本は0から9まで足して次の桁に移すが、境界の部分だけ目減りするので、目減り分を補正するとよい。
そろそろDPの切り取り方がしんどくなってきた。
F
真っ先に思いついたのは1が末尾に何個付くかを保持して長さでDPするというものだが、これだとO(NK)かかってダメ。そもそもK連続がダメということで、「1を停車駅、0を通過駅として、0,10,110,1110,...という長さ1からKまでのブロックを前から置くときの長さiの列の個数」と言い換えると、フィボナッチ的な漸化式で書ける。愚直にやるとまだO(NK)だが、K個のsumの部分を前の結果でO(1)でカウントできるので、これでO(N)となった！なお、両端が1という縛りがあるので、答えはDP[N+1]-2*DP[N]+DP[N-1]となる。
問題の言い換えが必要になってきた、しんどい。今回みたいに総和の形の遷移式は、前の結果を用いて定数時間でできることも多い。典型っぽいね。(差分を取ってるイメージなのかな)総和じゃなくても、maxとかでもできそう。
G
何も分からなかったのでギブアップ...部分列問題の解説を見る。
まず部分問題として、部分列数え上げを考える。重複を1通りで数えないといけないのがヤバいが、解決策は単純で「文字の順番で見て辞書式最小のものだけ数える」というもの。その上で、dp[i]を「i-1番目を必ず使って、0~i-1番目までの文字列でできるものの個数」とする。重複の制約より、答えはシンプルにdp[i]たちの和となる。
ここで、dp[i]で数えた文字列たちについて、次に文字cを付け加えた文字列を考えると、これは重複制約よりi番目以降で一番近い場所でカウントされる。よって、この場所next[i][c]が既知ならば、配るDPによりすべての部分列がカウントできる！next[i][c]については、うしろから順に見れば基本同じで、S[i]=cのときだけnext[i][c]=iなので、すぐに書ける。よってすべて合わせてO(N)で計算できる。
アイデアで大事なのは「複数あるもののうちカウントする1個を決める」「極端なものを選ぶ」ということか。重複を辞書式最小で選ぶというのは、要は一番左寄せで取っているんだ、というのが本質的みたい。
まずこの時点で難しい。しかしこの問題はさらに、K番目を取り出せと言っている、鬼か。
しかし、「復元するときは後ろからDPせよ」という典型がある。文字はチェックしないといけないので、DPとして「i番目以降で、先頭がcの文字列の個数」をカウントすればよい、ただし重複は最左を取ることにする。
こうすると、遷移はかなーり単純で、さっきのnextとかもいらなくなる。ってか、最初からこれでよかったのでは...復元についてもK個を超えてくる最小の文字を進んでいけばできる。
なんかこれだけ見れば思いついてもよかった気がするが、アイデアをまとめると、
「復元するときは後ろからDPせよ」
「複数あるもののうちカウントする1個を決めろ」
「極端なものを選べ」
というものになった。どれも典型っぽいが、組み合わさると難しい。今回は特に下二つが見えなかったのがダメだった。反省。
とりあえずここまで。ここからは結構難しそうなので、気が向いたら更新します。
