ABC-D 49-50 & Educational DP contest A-J
yahooコンD問題の連結DP、ABC-D 50の桁DPが解けなかったので、DPの強化を行うことにする。
D埋めの先人曰く
"DPは本当に色んなところで使いますので、最初に典型問題解くといいかも。
ということで
Educational DP https://atcoder.jp/contests/dp
Typical DP https://tdpc.contest.atcoder.jp
をやる。
Educational DPのほうが典型的で簡単なものらしいのでそちらから。
以下、解答メモ
ABC49
道路についてunion findしたあと、各鉄道についてのunion findを、その鉄道が道路について同じunionに属する街を結ぶ場合のみ併合
-> WA。
道路で連結されていない街を通じて列車が連結する場合を取り込めない。
道路と鉄道の両方で連結されているとすると、道路に関する代表元と鉄道に関する代表元が一致する。
multisetでやろうとしたらTLEしたが、mapにするとAC。
multisetは最悪の場合要素挿入にO(N)かかる。
ABC50
600点問題。
aとbを軸に考えたほうが良さそうだが、異なる(a,b)が同じ(u,v)を与えてしまう。
a = u, b = 0により、n = 0,..., Nについて、(u, v) = (n, n)を作ることができる。
a = u, b = 1は、 uがoddのとき(u,v) = (u-1, u+1) evenのとき(u+1,u+1)
よって、evenのときは重複がある。
a = u, b = 2は、u>>1 == 1のとき(u-2,u+2)、u>>1 == 0のとき(u+2,u+2)
a = u, b = 3は、
uの下2ビットが
11のとき(u-3,u+3)…u,vの差分6はまだ出てきていない。
01のとき(u-1+2,u+3) = (u+1, u+3)…u,vの差分2なので重複
10のとき(u-2+1,u+3) = (u-1, u+3)… u , vの差分4なので重複
00のとき(u+3,u+3) = (u+3, u+3)…u, vの差分0なので重複
(u and b) == bの場合に新しい(u, v)が生成できる。
一般のbについて考えても、 (u-b, u+b)になることが分かる。
N = 3の場合。
まず、自明な(u,v) = (n, n)が4種類。
b = 1で u, vが0以上N以下のものは u = 1, v = 2のみ
b = 2の場合は差分4の時点でアウト。
これで5つと分かる。
これをどう一般化するか。各uについてのループは不可能。
上の議論は結局、あるbについて、 (u and b) == bならば(u, v) = (u-b, u+b)が条件を満たすというもの。ただし、n-b >=0かつn+b<=N。
(u and b) == bを満たすuは計算できる。Nを超えない範囲でbでビットが0の部分を自由に0 or 1にするような選び方。
ただ、Nを超えないという条件判定の仕方がよくわからん。
-> あきらめ。
解説によると、桁DPというテクニックで解ける。
適用先は、今回のような
「ある整数 N以下の整数であって，ある条件を満たすものの個数を求めよ」
というタイプの問題で、桁数が巨大で全探索が不可能であるようなもの。
dp[見た桁数][N未満確定か] = 総数 というdpテーブルを作る。
例: N以下の整数を数える。
Nの最上位桁がDだったとすると、
dp[1][0] = 1 // 最上位桁がD
dp[1][1] = D-1; // 最上位桁が1, …, D-1
dp[2][0] = 1
dp[2][1] = 9 * (dp[1][1]) + (dp[1][0])*(D-1);
一般には、
dp[i+1][j || (d <D)] += dp[i][j];
ここで d <= ( j ? 9 : D)と書ける。
最終的にdp[N][0] + dp[N][1]が答えになる。
今回のD問題の場合、何ビット目かで桁dpを行う。
"dp[i][j] = a と b の i ビット目以上が決定していて、その段階で (v >> i) = (N >> i) − j となる通り数。"
とする。
条件判定が気色悪いが、要するに上の例で言うN未満のフラグに相当している。
1). a, bのiビット目が両方1の時、 jは (1<<i) *2増える。
2). 一方が1, 他方が 0の時、 1<<j 増える。
3). 両方0の時jはそのまま。
なので、N>>iとv>>iの差が0, 1, 2以上で異なる遷移。2以上の場合、その桁でa, b両方1でもN以下は確定している。
Nの i 番目のビットが 1 の時、
dp[i][0] = dp[i+1][0]
dp[i][1] = dp[i+1][0] + dp[i+1][1] //a, b一方を1にする + 両方0にする
dp[i][2] = 2*dp[i+1][1] + 3*dp[i+1][2] // i+1ビット目でNがvより大きければ、 1), 2)のどちらでもiビット目でこちらになる。
Nの i + 1番目のビットが 0 の時、
dp[i][0] = dp[i+1][0] + dp[i+1][1] // a, bを両方1にすることで、dp[i+1][1]から作れる。
dp[i][1] = dp[i+1][1] //a, bの一方を1にすることで、差は1に保たれる。 例えば10と01の差 = 1を考えれば良い。
dp[i][2] = dp[i+1][1] + 3*dp[i+1][2]
上位回答者のコードを見ると、vがN以下で条件を満たすものの数についてmapを使い
dp[n] = dp[n/2] + dp[(n-1)/2] + dp[(n-2)/2];
という処理をしている。桁で考えるのではなく、mapで直接値を扱っている。
もっとも右に新たにビットを追加することで n を作るという発想?
歯が立たない問題がことごとくDPなので、DP特訓に入ることにする。
----------------------------------------------------------------------
Educational DP contest
A - Frog 1
dp[i] = min {dp[i+1] + |h[i+1] - h[i]|, dp[i+2] + |h[i+2] - h[i]|}
を上から埋めていく。
B - Frog 2
Aを一般化する。
dp[i] = min {dp[i], dp[i+k] + |h[i+k] - h[i]|}
C - Vacation
前日の行動を記録した上で最大化する。
i 日目の行動が j だったときの最大値を持っておけば良い。
1日目から順番に埋めていく。
このぐらいの難易度なら良いけれど、Educationalを名乗るなら解説を用意して欲しい気もする。
D -Knapsack 1
ナップサック問題はAOJでもやった記憶。
Wの制約が小さいので、「 i 番目までの品物で重さw以下にするときの最大価値」というdpを考える。
dp[i][w] = max{dp[i-1][w], dp[i-1][w-wi] + vi}
答えはdp[N][W]
w-wi >= 0なら上記で、w-wi<0なら問答無用でdp[i][w]
int溢れに注意。
E -Knapsack 2
vの制約が小さいので、「i 番目までの品物で価値をv以上にする時の最小重量」とする。
dp[i][v] = min(dp[i-1][v], dp[i-1][v-vi] + wi}
最終的には、vの大きい方から見ていき、W以下の値が出たところのvを返せば良い。
(そのv以下の組み合わせはW以下で作れることが保証される)
F -LCS
以前AOJでやったはずなのだが忘れてしまった。
DP四天王の一つらしい http://www.deqnotes.net/acmicpc/1458/
s[0…y]とt[0…x]のLCS長を LCS(y,x)として考える。
このとき、 s[y] == t[x] と s[y] != t[x]の2パターンが考えられる。
前者の場合、LCS長はLCS(y-1, x-1) +1
後者の場合、LCS(y-1,x) or LCS(y,x-1)の大きい方。一方が大きければ対応する文字がLCSに入る。
LCS(x, y)のテーブルが埋まれば、LCSを具体的に構成できる。
dp[s.size()][t.size()]から出発して、 s[y] == t[x] なら s[y]をLCS列に追加。
dp[y][x-1] < dp[y-1][x]ならばt[x]がLCSに含まれるはずなので、yを減少させる。
DPの超典型問題。
G -Longest path
i 番目の辺の始点、終点を s, tとするとき、“tを終点とするlongest pathの長さ”がわかっていれば
dp[t] = max(dp[t], dp[s] + 1)という埋め方ができる。i 番目の辺が最長距離のパスで使われるならば後者、使われないなら前者
-> WA
新しい辺が入ったときにはtの先の最長距離が更新されるはず。
c -> s
a-> t -> bだったものが c -> s -> t -> bになったときに、bの最長距離が更新されなければならない。
pathの追加は処理が難しい。別の方針。
dp[s]: 始点をsとする最長パスの長さとする。
dp[s] = max(1 + sから直接移動可能な任意の tのdp[t])
ただし、どの順番で更新するかという問題がある。上の式でdp[t]の決定が先に行われていなければならない。つまり、post order dfsの順に更新する。ややこしい。
-> メモ化再帰で書けば更新順はあまり気にしなくて良い。
グラフの情報を値渡ししていてTLEした。Cの配列と違ってvectorはデフォルトでは値渡し。
このEducational DPコンテスト、1-indexedが多くて面倒。
H - Grid 1
dp[i][j]: (1,1)から(i,j)の最短経路の数
dp[i][j] = dp[i-1][j] + dp[i][j-1]
ただし、i, jが壁なら強制的にゼロ。
i, j の小さい順に埋めればok.
i = 1とj = 1は予め初期化しておく。
I - Coins
出力桁数に注意。
dp[1] = p1
dp[2] = p1*p2
dp[3] = p1*p2*(1-p3) + p1*p3+(1-p2) + (1-p1)*p2*p3 + p1*p2*p3
= p1* p2 + p1*p3+(1-p2) + (1-p1)*p2*p3
i+1 枚目を振ったあとで条件を満たすのは、
・i 枚目までで表が2枚以上多い (上の例でp1 * p2)
・i枚目までで表が1枚多く、i+1枚目が表
・i枚目までで表と裏の枚数が等しく、i+1枚目が表
の三通り。
ただ、桁dpのような場合と違い、2枚以上多くても別の状態に戻りうるので
double dp[N][N]を考える。
dp[i][j]を、i枚目まで振った段階で表がj枚のときの確率
とすると、漸化式は以下の形。
dp[i+1][j+1] = dp[i][j]*p + dp[i][j+1]*(1-p)
最終的には、dp[N][N/2+1, … N]の総和を出せば良い。
J - Sushi
サイコロの目に応じた状態遷移。
出力例1が既にヒントっぽい。
初期状態では全ての皿に寿司がある。
1つめの寿司は確率1で無くなる。
2つめの寿司は、1つめで取った皿に寿司があればまた確率1で無くなる。
１つめで取った皿にもう寿司がなければ確率(1-p)で無くなる。
…
i個目の寿司をとる操作回数の期待値を i-1個目から計算するにはどんな情報が必要か。
どの皿に寿司が残っているかがわかればよいが、それを記録するのは不可能。
何枚の皿に寿司が残っているかという情報だけで十分。
N枚のうちn枚に寿司が残っている場合、寿司を取るのに必要な操作回数の期待値は
1*(n/N) + 2*(n/N)(1-n/N) + 3 *(n/N) * (1-n/N)^2 + …
= N/n
i 個目の寿司を取ったときの考慮すべき変化は、各皿の寿司の個数が0個か否か。
もともと皿に2個以上の寿司があれば問題ない。
実際のところ、何番目の皿かは重要ではない。寿司の個数ごと皿を分類する。
dp[i][a][b][c]を、寿司1, 2, 3個の皿がa, b, c枚の状態でi個目の寿司を取る操作回数の期待値とすると、
dp[i+1][a][b][c] は、 dp[i][a+1][b][c], dp[i][a-1][b+1][c], dp[i][a][b-1][c+1]
によって求められる。左から順に、寿司1個の皿、2個の皿、3個の皿から取る場合。
-> コードは書いたが、条件判定が面倒すぎる。デバッグしきれない。
解答に必要な情報は全て揃っているが、実装力不足で解ききれない(未熟)。
メモ: EDPコンテストの解説記事
やはり、dpの更新順序が非自明な場合にはメモ化再帰が良いらしい。
メモ化再帰ではdfsして遷移状態がなくなったものからテーブルが埋まっていくので、自動的にトポロジカルソートの逆順での更新になる。
DPとはつまるところ、何らかのDAGをトポロジカル順序(ないしその逆順)に探索することといえるっぽい。
DPで解けるか否かの判断基準としてDAGになっていそうか考えるというのが使えそう。
DP特訓で意識すべきこと:
配るDPとか貰うDPとかの概念を理解し、解いた問題を類型化する。
