Typical DP Contest ひとこと解法集

まとめました。
1
rng_2 @rng_58

A: dp[i][j]: 最初の i 問からいくつか選んで和を j 点にできるか?

2013-09-01 01:21:44
rng_2 @rng_58

B: dp[i][j]: 左の山が i 個、右の山が j このこっている状態からスタートするときの先手の取るものの価値の和

2013-09-01 01:22:45
rng_2 @rng_58

C: dp[i][j]: i 人目が j ラウンド勝ち進む確率

2013-09-01 01:23:17
rng_2 @rng_58

D: dp[n][i][j][k]: サイコロを n 回投げたときの和が 2^i3^j5^k である確率

2013-09-01 01:24:03
rng_2 @rng_58

E: 左から一桁ずつ追加していって、dp[i][j][smaller]: i 桁目まで追加して、mod D の和が j とする方法は何通りあるか、N より小さくなった時点で smaller を true にする

2013-09-01 01:26:51
rng_2 @rng_58

F: 逆に止まらないところを考える。部分和

2013-09-01 01:27:27
rng_2 @rng_58

G: dp[i][c]: i 文字目以降の部分列で文字 c から始まるものの個数、というテーブルを用意してから復元

2013-09-01 01:28:24
rng_2 @rng_58

H: 説明しにくいのでコードを読んでください

2013-09-01 01:31:13
rng_2 @rng_58

I: dp[i][j]: i から j 文字目を完全に消せるか、幅の小さいほうからやる

2013-09-01 01:31:52
rng_2 @rng_58

J: dp[mask]: mask (2^16 の部分集合) に物が残っているときに全部倒すのにかかる回数の期待値、自分自身を含む式が出てくるので適当に式変形

2013-09-01 01:33:37
rng_2 @rng_58

K: 右端でソートして左端のリス

2013-09-01 01:34:44
rng_2 @rng_58

L: 猫 i から距離 1 以内の猫のうち最も左のものを猫 l[i] とすると、l[0] <= l[1] <= ... <= l[N-1] が成り立って、逆にそれで十分であることが分かるので、これを利用して DP、

2013-09-01 01:36:57
rng_2 @rng_58

M: 同じ解で部屋 i から部屋 j 間で行く経路の数を bit dp で求めてから行列累乗

2013-09-01 01:38:48
rng_2 @rng_58

N: "辺 e にたいして片側" のような形をしている各部分木について、そこに含まれる辺の個数と辺の順番の決め方の個数を求める

2013-09-01 01:41:03
rng_2 @rng_58

O: dp[i][j]: 最初の i 文字をならべたとき、同じ文字が隣り合っている場所が j 箇所あるようにする方法は何通りか

2013-09-01 01:41:57
rng_2 @rng_58

P: 適当に根をつけて、dp[x][i][j]: x を頂点とする部分木からパスを j 本選び、x での次数が j になっているようにする方法は何通りか

2013-09-01 01:43:03
rng_2 @rng_58

Q: 最後の 7 文字と、最後の 8 箇所の区切り位置のうち文字列の境界となる可能性のある部分 (2^7 * 2^8) を状態としてもって一文字ずつ追加していく

2013-09-01 01:44:18
rng_2 @rng_58

R: 強連結成分に分解して、DAG にする。DAG 上の二つの頂点の場所を状態としてもっておいて、頂点を進めるときは今進んでいるほうの頂点を越えるようにする

2013-09-01 01:46:41
rng_2 @rng_58

S: 6 個の行の接続関係を覚えておく面倒なことで有名な DP

2013-09-01 01:47:33
rng_2 @rng_58

T: x^N を (x^K - (1 + ... + x^(K-1)) でわったあまりを c_0 + c_1x + ... + c_(K-1)x^(K-1) とすると、a_N = c_0a_0 + ... + c_(K-1)a_(K-1) が成り立つ...

2013-09-01 01:49:41

コメント

コメントがまだありません。感想を最初に伝えてみませんか?