kwm_t

kwm_tのメモ

TDPC

■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 - フィボナッチ

きたまさ法というらしい

人様のライブラリパクって勉強。