Educational DP contest K-O
DP問題の考え方 (DP = DAG上の探索 として)
メモ化再帰では、トポロジカル順を意識する必要がない。
ループもメモ化再帰もどちらも、時間計算量O(E+V)、空間計算量(V)で同じ。
また、どちらか一方でなければ解けない問題というのはほぼ無い。
ループの利点としては、漸化式の評価が重いときに適切なデータ構造を使って高速化できる場合があることらしい
あと、メモ化だと再帰が深すぎると走らない(K問題が例)
今日は5問。少し慣れてきた。
bit DPのような基本的なテクニックをサクッと書けるようにしたい。
ゲーム問題がいくつかあるが、色々と記事を読んでいるとgrundy数やらの用語が出てくる。どこかで自分なりにまとめて練習を積みたいところ。
以下、解答メモ。
K - Stones
ゲーム木上のdp問題。
Aの元は何度でも使うことができる。
石の個数は増えない -> DAG
終状態では、石の残数がa1未満になっている。
最適に行動するという仮定をどう考えるべきか。
K = 1,…, a1-1では secondの勝ち。
K = a1, …, a1+a2-1ではfirstの勝ち
1ターンで勝負がつかない場合の行動は？
残りの石が k 個の時に firstの手番だったとする。
firstには、石を k-a1, …, k-anにする選択がある。
これらのうちで、その後のゲーム展開で必勝のものがあればそれを選択すればよい。
最適行動かつ引き分けなしというゲーム設定なので、kの更新時点でk-a1…k-anのすべてに勝敗が割り当てられている。
dp[k]: 残りk個のとき次に操作する人が勝つか否か、で考えてみる。
自明なケースの初期化は
dp[1…a1-1] = false
dp[a1…a1+a2-1] = true
...
dp[a1…a1+aN-1] = true
非自明なものは、
dp[ k ] = (if any dp[k-ai] = true)? true: false
可能な選択全てで負ける場合にfalseとする
更新順が自明な場合はループで書いたほうが良さそう。
上の議論は、ゲーム問題におけるWL Algorithmというものにほかならないっぽい。
L - Deque
大きい順に取っていくだけだと、
10 100 1 9のようなケースで相手に100を取られてしまう。
残った数列の先頭要素と末尾のインデックスを l, rとしたとき、
dp[l][r] = X - Yとなるようにしたい。
手番をどう管理するか。 r- l + 1 %2 == N%2なら先手
先手番
dp[l][r] = max( dp[l+1][r] + a[l], dp[l][r-1] + a[r])
後手番
dp[l][r] = min( dp[l+1][r] - a[l], dp[l][r-1] - a[r])
更新順は、[l, r]が狭い順。[l, l +d]としてdのループ -> lのループ
M - Candies
K個の区別できないボールを … に似ているが、一人に配れる飴の個数に上限がある。
寿司問題に似ている気がする。aiごとに分類する？
子供を区別する必要があるのと、k = 1, …, Kについて上限k個の子供が何人いるかを管理するのは難しい。
実験
K = 1の時、ai != 0の子供の数 x だけ配る方法が存在する。
K = 2の時、
K=1で配った結果としてキャパが0になった子供が存在する場合は x(x-1)
そうでない場合は x^2
子供についてdpしたほうが良さそう。
dp[i][k]: i人目までの子供にk個配る配り方
とすると、
dp[i+1][k] = Σ dp[i][k-x] ここでx = 0,…, a_{i+1}
が成立する。ただ、計算量が間に合うか不安。右辺は一般にO(K)必要。
保有可能量に関して子供をソートしておくことにする。
i = 1でのkの上限は a1で、i = 2の計算にはdp[1][0]…dp[1][a1]が必要。
i = 2でのkの上限はa1 + a2で、 i =3の計算には dp[2][0]…dp[2][a1+a2]が必要。
dp[i][y]が寄与する右辺を一度に扱えればよい。
dp[i][y]は、dp[i+1][y] …, dp[i+1][y + a_{i+1}]に寄与する。
dp[i][y]の累積和を計算しておけば、dp[i+1][ z ] はO(1)で更新できる。
dp[i+1][z] = cumSum(z+a_{i+1}) - cumSum(z-1)
cumSumがあればdp[i]の値は必要ないので、dp[x]をN回更新してdp[K]を求めれば良い。
累積和を使う以外に、漸化式を変形し、dp[i][y]をdp[i][w<y]を使って更新することでO(1)にすることもできるらしい
無理筋かどうかを判断するには回数こなすしかないのだろうか。
N - Slimes
AOJで見た行列連鎖積問題に似た雰囲気を感じる
終状態は大きさ a1 +... + aNのものが一つだけ。
最適手順での最初の1ステップが ak とak+1の間だったとすると、
[a1, …, ak-1], [ak + ak+1], [ak+2…aN]という問題に分割される。
dp[l][r]を [al…ar]を最適に結合させるときのコストとするならば解はdp[1][N]であり、
結合させる位置kに関して
= min_k dp[1][k-1] + dp[k+2][N] + sum(a1…aN)
dp[l][r] = min_k dp[l][k-1] + dp[k+2][N] + sum(al…ar)
sum(..)はaの累積和を計算しておけばO(1)
更新順が非自明なので、これをメモ化再帰によって解く。
-> 上の漸化式だと、入力例１のように一つずつ潰していくケースが入らない。
“最後”に潰すボンド k について場合分けして考える。
このとき、操作前の時点で
[1…k]、[k+1…N]がそれぞれ一つのまとまりになっている。kを潰すことで
[1…N]となり、それには sum(1…N)のコストがかかる。
どのkが最適か？
1…kの中での潰し方とk+1…Nの潰し方は互いに独立にコストを最小化できる。
よって、最終状態から逆に辿っていくことを考えると、
dp[l][r] = dp[l][k] + dp[k+1][r] + sum(al…ar)でよい。
解答に時間がかかりすぎてしまった。
再帰的な併合は、スライムの重量変化を扱いきれない。
O - Matching
i 人目まででマッチングが成立しているときにi+1人目が追加されるとどうなるか。
(Mのi+1とFのi+1がマッチ): (1..i 人目までの任意のマッチングパターン)
(Mのi+1とFのj, MのkとFのi+1がマッチ): (a_{i+1,j} == 1かつa_{k,i+1}を満たす j, kの組から作られるマッチングパターン)
後者をどう計算するかがキモ。
j, kの候補ごとに結果が異なる。 Fの1…j-1, j+1… i とMの1…k-1, k+1…iのマッチング総数 f(i,j,k)が必要。
制約が小さい(N <= 21)ことに着目。
各 i で、全ての可能な選択 N_C_i のそれぞれにマッチング総数を求めておけば、
i+1で上の計算をする場合にはそれを参照するだけでいい。
N_C_iで処理するの面倒そう。O(N 2^N)で通る？
-> 男女両方考慮すると2^2Nになるので無理。
combinationで真面目にやれば大丈夫? k, jは1…iの中で1つづつ選ぶだけ。
dp[i][j][k]を、i人目のマッチングであって Fのj番目、Mのi番目を使わない組み合わせの数
とする。dp[i][0][0]に全員使った場合の値を入れる。
dp[i+1][0][0] = if(a_{i+1.i+1} == 1, dp[i][0][0]) + SUM(dp[i][j][k] where a_{i+1,j} == a_{k,i+1} == 1);
dp[i+1][j][k]をどう埋めるかが問題。
dp[i][j][k]は、dp[i][0][0]のうちでマッチングがj - jかつk-k or j-k かつk-jのものの数に等しい。
-> 不可能ではなさそうだが実装が複雑すぎる。精神が折れた。
想定解はbit DP
dp[i][mask]: i番目のMまで見たときに、既に使用したFを表すビットマスク
これでO(N 2^N)になる。
i個のビットが立っている状態からの遷移だけ見れば良いので、キューで管理する。
制約から2^Nという予想 -> bit DPでは？という思考ができるように。
