Typical DP Contest (TDPC)

Typical DP Contestとは,りんごさんが作ったDPの問題で典型的すぎて一般的なコンテストに出せないと(りんごさんが)判断した,DPの練習問題を集めたものです が,十分難しい難易度のものもあります.

2013/8/31に開催されたんですがようやく全問解いたのでメモ.(もう昔解いた問題は忘却してそう)

良問揃いなので,まだ解いてない人は是非自分で考えてみてください.

A:dp[i][j]=i問目まででj点を取れるか
B:dp[i][j]=左からi個,右からj個取った時最大で残り何点取れるか もらうDP
C:dp[i][j]=iラウンド目でjが勝っている確率
D:dp[i][a][b][c]=i回振った積に2がa個,3がb個,5がd個出てる確率
E:dp[i][j][k]=i桁の数字で,桁和modDがjでk=0なら上i桁と完全一致,1なら上i桁未満 の場合の数
F:dp[i]=i駅目までの止まり方(i駅目に止まらなくても良い) dp[i]からdp[i+1]への遷移は,基本i+1に止まるか止まらないかで2倍だが,直近K-1駅全て止まってる場合はとまっちゃダメで,その場合の数はdp[i-K]と一致する.答えは最後止まる必要があるのでdp[N]-dp[N-1] (最後止まらないようなものはdp[N-1]と一対一対応するので)
G:dp[i]:後ろからi文字の部分文字列は何通りあるか が,「新たに付け加えた文字を使わなくても元々出来ていた文字列」の数が,その付け加えた文字の種類のうち直近に出てきたとこ(その文字自体は含まない)までの部分文字列の数と等しいことを考えると計算できる.あとは辞書順で行けるかどうか判定.
H:先に色でソートしておく,dp[i][j][k][l]=i個まで見てj色使って重さがKでl:(今見ている色を既に使ったか)
I:dp[l][r]:s[l,r)を完全に取り除けるか? あるkがあってs[l,k)とs[k,r)が完全に取り除ける場合 というのと, s[l]=s[r-1]='i'であって,あるkがあってs[k]='w'でs[l,k)とs[k+1,r)が完全に取り除ける という遷移の二通り考えればOK.
J:bitDP. dp[i]=iが残ってる時に倒すまでの期待値. 自己ループが発生するので移項して係数かける.
K:冷静に考えるとただのLIS.dp[i]=長さiの列の最後の最小 でにぶたんO(NlogN)
L:dp[i][j]:i匹置いてi匹目と距離1以内にいるうち最も左の猫がj の時のうれしみのmax. i+1を置くとき,j以降に関しては自由に入るかどうか選べる.
M:セールスマン的なbitDP dp[i][j][k]="i->jでsubset kを通る" +行列累乗.
N:dp[v][i]=頂点v以下の部分木で,vとvの親が個の中でi番目に繋がれる場合の数 というのを計算した気がするのだが,iをもたなくてもrootを全部試してrootからやっていけばいいことに気づいた.
O:挿入dp. dp[i][j]=i種類目の文字までを並べた時に同じ文字が隣り合ってる箇所がj箇所 の場合の数. 挿入するときにj箇所中何箇所を切断するか とi文字目を何グループに分けるかを全部試すと遷移が出来る.
P:dp[i][j][k]=iの部分木でj本書いてて,iから下にはk本生えてる(k=0,1,2). 各頂点での更新も個数数えるdp.
Q:一番最後に解いた問題.(S,Rが2015/11とかだったので半年以上あいてる) dp[i][s][b]=i文字目まで見て最後の8文字がsで,"x文字後ろから削ったものも作れる(x=1~7)"のbitがb の時の場合の数. 更新を書く文字列に対してクッソ頑張ってたんだけど,冷静に考えると一文字ずつ増やしていけることがわかる.
R:慣れてたら最小費用流の方が簡単かも.まず強連結成分分解.あとはDAGで頂点重み付きだと思えて,2回の操作を同時に行うと思って,dp[v][u]=点v,uにいくまでのうれしみのmax なのだが,ここで遷移を適当にすると二回通った頂点を重複してカウントしてしまうことがある.vがuの先祖 or uがvの先祖の時こういうことが起こるのだが,よく考えると,v=uと,vはuの先祖でない∧uはvの〃 の場合の二通りに制限しても任意の操作を表す遷移が可能であることがわかる.
S:各横マスの連結状態を持つ面倒なdp.ベル数はまあまあ小さい.正規化が面倒なので遷移が面倒.あと1行一気に塗るんじゃなくて一マスずつ塗ると楽だし計算量も落ちる.
T:きたまさ法と呼ばれる奴.n-ボナッチ行列の累乗をするとO(K^3logN)でダメ.a_iをa_0~a_{K-1}の線形和で表すことを考えると,a_iの表示からa_{i+1}とa_{2i}の表示がO(K^2)で求まるので,全体でO(K^2logN)になる. みさわさんが言ってた,(Z/pZ[x])/(x^K-x^(K-1)-...-1)という環でのべき乗だと思う というのが数学よりの人にはわかりやすいと思う.

コード載せたら爆発炎上するのでおわり.

今だと典型DPにはさらに色んな物が含まれそう.思いついたのを上げると,segtree高速化,convex hull trick,monge,誤差による状態量減らし,xの範囲がクソでかくてdp[x]=vになるxの集合がいい感じの性質を持つとき,dp[性質]=xたち みたいにする とかかなあ