■A - コンテスト
dp[i][j] := i問目までの組み合わせでj点を作れるならtrue
true == dp[i][j]なら
dp[i+1][j]とdp[i+1][j+P[i]]をtureに遷移
■B - ゲーム
dfsっぽい感じで
dp[i][j] := Aがi個、Bがj個残っている状態で最善を尽くした時のすぬけくんの得点と定める
■C - トーナメント
dp[i][j] := i回戦が終わった時にjが勝ち残っている確率
■D - サイコロ
dp[i][j][k][l] := i回投げ終わった状態の積が2^i*3^j*5^kな確率
■E - 数
桁dpd
p[i][j][k] : =i桁目まで見た、j = 0はNと一致,j = 1はN未満確定、桁和のmodがk
■F - 準急
FPSで解くとなにも考えなくていいです
dp[i] := 条件を満たして最後に駅iに停車しない場合の数
dp[i] = dp[i-1] + dp[i-2] +........dp[i-k] = sumdp[i-1] - sumdp[i-k-1]
答えはdp[N-1] + dp[N-2] + ......... + dp[N-(K-1)] = sumdp[N-1] - sumdp[N-K]
■G - 辞書順
ここから少し難しくなった?
dpというよりはグラフ
サンプルのeelだと頭に空文字があると見て
*eelの4文字と解釈し
0->1,0->3,1->2,1->3,2->3に辺を貼る
これでe,ee,eel,el,lが作れるので
あとは適当に後ろからdp
そしてdp結果から答えの文字列を作成
*eelでdpが順に5(e,ee,eel,el,l),4(e,ee,eel,el),2(e,el),1(l)
■H - ナップザック
ナップサック+α
O(NCW)?
dp[i][j] := i色を使って、重さj以下の条件下での価値の最大値
色を小さい方から順番にdpを更新していく。
■I - イウィ
区間dp
dp[l][r] := [l,r)間での消せる数の最大値
dp[l][r] = max(dp[l][i] + dp[i][r]);
これだけだと駄目なので
'i' + [l+1,i) + 'w' + [i+1,r-1) + 'i'
のような形で両区間([l+1,i) ,[i+1,r-1))が全て無くなるならそれも遷移に組み込む必要がある。
■J - ボール
bitdp
dp[i] := 状態i(立ってるビットが倒されたbit)から終了するまでにかかる期待値
としてdp[1<<N-1] = 0を初期値にし、dp[0]を求めたい
遷移は各状態から各座標にめがけてボールを投げ続け
dp[i] = min(1 + (dp[next1] + dp[next2] + dp[next3])/3)
なイメージ
next1 == iになるケースがあるのでそのケースは移行してうまいことやること。
■K - ターゲット
LIS
円iの範囲は(xi - ri,xi + ri)
右端(xi + ri)の大小で左端(xi - ri)のソートを行い
できた配列の最長減少部分列のサイズが答え
増加部分列するためにri - xiになるようにして渡す必要がある。
■L - 猫
dp[i][j] = jからiまでは距離1にいるという条件の下での最大値
dp[i][j] = dp[i - 1][k] + f[i][j] + f[i][k+1]........f[i][i]
= dp[i - 1][k] + sum[i][i+1] - sum[i][j]
■M - 家
行列の積
dp[i][j] = jからiに行く場合の数として
行列の掛け算
■N - 木
dfsの戻りに部分木のサイズとそこ以下の木の答えをもたる
それぞれが{s0,a0},{s1,a1},{s2,a2}だったとして返すのは
{s0 * s1 * s2 * c(s0 + s1 + s2 , s0) * c(s1 + s2 , s1) * s(s2 , s2),a0 + a1 + a2}
■O - 文字列
dp[i][j] = i種類目までの文字を使って同じ文字が隣り合っている箇所がj個ある場合の数 配るdp
dp[i + 1][j + (F[i] - k) - l] += dp[i][j] * c(F[i] - 1,k - 1)*c(j,l)*c(L[i] + 1 - j,k - l)
k:=分割数(増える連続箇所 = F[i] - k)(1 <= k <= F[i])
l:=連続している位置に突っ込む数
■P - うなぎ
木dp
dp[i][j][k]:=iより下の部分木にて条件を満たすパスがj本あって頂点iから出てるパスの本数がkと
置くとdp[0][K][0] + dp[0][K][1] + dp[0][K][2]が答え
■Q - 連結
dp[i][j][k]:=i文字目までできている、直近7文字はj、単語の区切り位置はk
■R - グラフ
めっちゃ難しい
強連結成分分解して閉路を潰してdagを作る
作ったdagをトポロジカルソート
dp[i][j] := 今いる位置がiとjの時の最大値(jはトポロジカル順序的にiを超えない)
伸ばし先のkは直接結べなくても間接的に伸ばせれば良いこと
kはトポロジカル順序的にi、jを超えることを満たしつつことに注意しつつ
dp[k][i or j]に遷移
■S - マス目
これも難しいHの制約が小さいので4^6ぐらいは状態数として持っても大丈夫そう
白マスを0、黒マスを1 or 2 or 3とし(下の定義通りにすると4以上が不要なのも明らか(1は絶対必要なので))
1の黒マスが右上と連結している、同じ値の黒マス同士は連結していて、異なるものは連結していないとして
dp[i][j]:=i行目の状態がj
と置く
状態数が4^Hあって遷移がそれぞれ黒or白なので2^Hあるので
先に4^H*2^6パターンの遷移を全て洗いだしておいて(前計算)
遷移させる。
遷移よりも前計算が大変です。
■T - フィボナッチ
きたまさ法というらしい
人様のライブラリパクって勉強。