Educational DP Contest / DP まとめコンテスト〈EDPC〉

1/6(日)20:00-25:00

始まった時点で家に帰る途中で20:14に参戦。
途中30分弱離席したけれど結局最後までやってて全26問中16完で172位
フル参加できてたら+1〜2問ってところか。

終わってから残りの問題にもひと通り目を通したけれどまだ習ってないテクが必要な問題がある。ぜひ今回持って帰りたい。
→ Educational DP Contest / DP まとめコンテスト〈EDPC〉補習篇（T,U,V,W,X,Y,Z） - naoya_t@hatenablog

A - Frog 1 (100)

A - Frog 1

dp[i]=足場iまでのコストの最小値
dp[1]=0
答えは dp[N]

更新はO(1)なのでO(N)
→AC 20:18:40
https://atcoder.jp/contests/dp/submissions/3937651

B - Frog 2 (100)

B - Frog 2

dp[i]=足場iまでのコストの最小値
dp[1]=0
答えは dp[N]

更新は $O(K)$ なので $O(NK)$
→AC 20:22:40
https://atcoder.jp/contests/dp/submissions/3937999

C - Vacation (100)

C - Vacation

dp[i][j]=i日目に活動j{a,b,c}をした時のi日目までの最大幸福度
dp[0][j]=0
答えは max(dp[N][0..2])

更新はO(|活動の種類|)= $O(1)$ で $O(N)$
→AC 20:30:24
https://atcoder.jp/contests/dp/submissions/3938669

D - Knapsack 1 (100)

D - Knapsack 1

dp[w]=重さwでの最大価値
dp[0]=0
答えは max(dp[0..W])

$O(WK)$ で
→AC 20:36:52
https://atcoder.jp/contests/dp/submissions/3939241

E - Knapsack 2 (100)

E - Knapsack 2
Wが大きいのでDの手が使えないというやつだね（蟻本にもあるね）

dp[v]=価値vになる最小の重さ
dp[i]=∞
答えは argmax(dp) where dp≠∞

$O(N\cdot v_{max})$ で
→AC 20:40:59
https://atcoder.jp/contests/dp/submissions/3939553

F - LCS (100)

F - LCS
編集距離を求める要領で

dp[i][j]=sをi文字,tをj文字読んだ時点での最長の部分文字列の長さ
prev[i][j]=どっちから来たか（上,左,斜め上）
求める文字列の長さは dp[|s|][|t|]
答えは prev[|s|][|t|] から遡って構築

$O(|s|\cdot|t|)$ で
→AC 20:57:54
https://atcoder.jp/contests/dp/submissions/3940817

G - Longest Path (100)

G - Longest Path
悩む

出る道しかないノードと入る道しかないノードを集めて
入る道しかないノードから逆に辿っていって
訪問済みノードに来たら、それまでの移動距離とそこから終点までの距離を足したものを終点（出る道しかないノード）に記録
答えは終点の記録の最大値

$O(M)$ ？（自分の実装は $O(MlogN)$ っぽい）
→WA(1) 21:26:52
先に他のやつ見るか

終了後

これは難しく考えすぎてた
ある頂点uからの最長距離（深さ）を求める関数をdepth(u)とすると
depth(u) = max(0, 1+depth(u.child1), 1+depth(u.child2), ...)
でこれは当然メモ化なりDPなり出来るしすぐ終わる（ $O(N+M)$ かな）
→AC
https://atcoder.jp/contests/dp/submissions/3954531

H - Grid 1 (100)

H - Grid 1

dp[i][j]=マス(i,j)まで来る経路が何通りあるか
dp[1][1]=1
答えは dp[H][W]

上と左の値を（壁でなければ）足していくのみなので更新は $O(1)$ 、全体で $O(HW)$
→AC 21:33:57
https://atcoder.jp/contests/dp/submissions/3943176

I - Coins (100)

I - Coins

dp[i][c]=i枚目まで投げた時点で表がc枚出ている確率
- dp[i+1][c+1] += p_i * dp[i][c]
- dp[i+1][c] += (1 - p_i) * dp[i][c]
dp[0][0]=1, dp[それ以外]=0
答えは sum(dp[N][ceil(N/2)..N])

更新は $O(1)$ なので $O(N^2)$
空間は節約すれば $O(N)$
→AC 21:40:35
https://atcoder.jp/contests/dp/submissions/3943534

J - Sushi (100)

J - Sushi
皿が300種類、それぞれ最大3枚（最小1枚）。

dp[a][b][c]=3枚ある皿がa種類、2枚ある皿がb種類、1枚ある皿がc種類あるとき、そのすべての皿が無くなるまでの操作回数の期待値
- dp[a][b][c]=1 + (a/N)dp[a-1][b+1][c] + (b/N)dp[a][b-1][c+1] + (c/N)dp[a][b][c-1] + ((N-a-b-c)/N)dp[a][b][c]
- dp[a][b][c]が両辺に出てくるので左辺にまとめて両辺を(a+b+c)/Nで割って
dp[0][0][0]=0
答えは dp[count(3枚ある種類)]count(2枚ある種類)]count(1枚ある種類)]

→AC 22:09:07
https://atcoder.jp/contests/dp/submissions/3945006

K - Stones (100)

K - Stones

Grundy数を考える
g[0]=0
g[x]=山にx個の石が残っている時のGrundy数
g[N-a_i]の中に1つでも0があれば太郎君の勝ち

Grundy数を求めるのが1回 $O(N)$ として全体で $O(NK)$ で間に合うはず
→AC 22:26:57
https://atcoder.jp/contests/dp/submissions/3945791

そんなに難しく考えなくても

勝ち負けとか最善手とか詰めて考えるのが苦手な自分でも分かる書き方で

vector<int> a;

bool taro(int k);
bool jiro(int k);

bool taro(int k) {
    for (int ai: a) {
        if (ai > k) continue;
        if (!jiro(k-ai)) return true;
    }
    return false;
}

bool jiro(int k) {
    for (int ai: a) {
        if (ai > k) continue;
        if (!taro(k-ai)) return true;
    }
    return false;
}

int main() {
    int N, K; scanf("%d%d", &N, &K);
    a.resize(N); rep(i,N) scanf("%d", &a[i]);
    cout << (taro(K) ? "First":"Second") << endl;
    return 0;
}

taro(k) は残りK個のときに太郎が勝てるか否か。
jiro(k) は残りk個のときに次郎が勝てるか否か。

$a_i$ 個取って相手に手番を回して相手が勝てない $a_i$ があれば自分の勝ち、というだけの話で、当然ながら taro() と jiro() の中身はほとんど同じなので今どちらの手番かを引数にしても構わないのだけれど、それだと自分の脳が理解を拒否するので taro() jiro() 方式を編み出した。
これをメモ化するなり何なりすれば出来上がり。
https://atcoder.jp/contests/dp/submissions/3967626

L - Deque (100)

L - Deque

dp[i][j]=区間[i,j)が残っている場合の最適X-Y
答えは dp[0][N]

taro()/jiro()を交互に呼ぶメモ化再帰で書いた
→AC 22:41:46
https://atcoder.jp/contests/dp/submissions/3946436

M - Candies (100)

M - Candies

dp[i][c]=i人目までに合計c個分ける方法
dp[0][0]=1
答えは dp[N][K]

dp[i+1][..] = NTT.convolution(dp[i][..], [1,1,...(全部で $a_i+1$ 個の1)] で更新しようとしてローカルで最悪ケースがTLE
飛ばして次へ

終了後

あ、掛ける値は全部1だから、１つずつずらした和というか累積和を使えば計算量少なめで綺麗に？書けるじゃん（累積和計算に1人 $O(K)$ 、それを利用した掛け算で1人 $O(K)$ 、N人いるので $O(NK)$ ）
→AC（25:07:02）
https://atcoder.jp/contests/dp/submissions/3950611

N - Slimes (100)

N - Slimes
こないだLeetCodeで埋めた風船の問題に似てる

dp[i][j]=区間[i,j)のスライムを全て合体させるコストの最小値
- dp[i][j] = min(dp[i][k] + dp[k][j] + $\sum_i^{j-1} a_i$ )
- iとjの間のkを全部試して、求める区間より小さい2つを合体させるコストを見ていく
dp[i][i+1]=0
答えは dp[0][N]

$O(N^2)$ か
→AC 23:23:51
https://atcoder.jp/contests/dp/submissions/3948001

O - Matching (100)

O - Matching

dp[i][s]=i人目の男性まで見て、ペア確定済みの女性が集合sで表される時、そこまでの組み方が何通りか（※男女どちらの視点から見ても一緒）
dp[0][0]=1
答えは dp[N][2^N-1]

N人で、集合が2^Nパターンで、中でビットをN箇所見るから $O(N^22^N)$ か
サンプルケースは通るけどN=21のケースを作って試したらTLE
集合のパターンでpopcountがiのやつだけ見るようにすれば1/Nできて $O(N2^N)$ でハッピー
→AC 23:44:24
https://atcoder.jp/contests/dp/submissions/3948663

P - Independent Set (100)

P - Independent Set

dp[n][黒|白]=頂点nを黒|白で塗った場合のその頂点を根とするsubtreeの色の組み合わせ数
- dp[n][黒]=prod(dp[n][白]) ←子ノードがすべて白でないと不可能なので
- dp[n][白]=prod(dp[n][黒]+dp[n][白])
dp[葉][黒]=dp[葉][白]=1
答えは dp[根][黒] + dp[根][白]
- どの頂点をrootにしても構わない

計算量は根の数の合計+子供の数の合計に比例するので $O(N)$
→AC 24:07:53
https://atcoder.jp/contests/dp/submissions/3949308

Q - Flowers (100)

Q - Flowers
飛ばした

終了後

h_i未満の範囲で高さが単調増加な花集合の美しさの総和の最大値（不可能なら0）が得られれば、h_iをそれに追加していくだけでいい。RMQを動的に更新していけば行けるね
セグ木RMQで
$O(NlogN)$ か
→AC
https://atcoder.jp/contests/dp/submissions/3951166

R - Walk (100)

R - Walk
愚直に1000回ぐらいやってパターンが見えるかとか思って書きながら
もしかして：行列累乗
入力の $a_{i,j}$ を行列AとしてK乗して、[1,1,1,1,..] に掛けて得た値を合計するだけ
$O(N^3)$
→AC 24:34:58
https://atcoder.jp/contests/dp/submissions/3949953