naoya_t@hatenablog

いわゆるチラシノウラであります

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

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

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

終わってから残りの問題にもひと通り目を通したけれどまだ習ってないテクが必要な問題がある。ぜひ今回持って帰りたい。

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つずつずらした和というか累積和を使えば計算量少なめで綺麗に?書けるじゃん(累積和計算に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

S - Digit Sum (100)

S - Digit Sum
はい桁DP
// 参考:桁DP入門 - ペケンペイのブログ

  • dp[i][j][k] = i:i桁目まで見た j=K以下確定済か k=Dで割った余り の個数
  • dp[0][0][0] = 1
  • 答えは dp[Kの桁数][0][0] + dp[Kの桁数][1][0] - 1
    • 1を引くのは個数の中に0が含まれているから。(0は常にDの倍数)

O(|K|D)
→AC 24:47:23
https://atcoder.jp/contests/dp/submissions/3950198



補習編

コンテスト後に読んだ問題たち。ここで出てくるテクニックもこの機会にぜひ身につけておきたい。
(あとで解く)

参考:
www.hamayanhamayan.com

T - Permutation (100)

T - Permutation

<><

かわいい
それはさておき

  • dp[n][k] = n番目(n≧1)まで来たときに長さnで最後がその中で小さい方からk番目(1≦k≦n)であるパターン数
  • dp[1][1] = 1
  • n番目が < のとき:
    • dp[n][1] = 0
    • dp[n][k] = dp[n][k-1] + dp[n-1][k-1] for k>1
  • n番目が > のとき:
    • dp[n][n] = 0
    • dp[n][k] = dp[n][k+1] + dp[n-1][k+1] for k<n
  • 答えはΣ dp[n][1..n]

O(N^2)ですね
→AC
https://atcoder.jp/contests/dp/submissions/3962656

U - Grouping (100)

U - Grouping
うさぎ16匹の相性を加味したグループ編成

  • all[集合]: その集合に含まれるうさぎを全て同じグループに入れた場合のスコア
    • bitDPっぽく求められる。O(N\cdot 2^N)
  • dp[集合]: その集合に含まれるうさぎを同じグループに入れたり入れなかったりでの最高スコア
    • dp[集合]=all[集合] から始めて、区間DPっぽい感じで max(dp[部分集合] + dp[補集合]) みたいに更新していく (その + の部分は同じグループにならない境目と考えられる)
    • O(2^{2N})っぽくない?
      • dp[集合]の計算は集合のサイズをkとすると _{16}C_k \frac{2^k}{2} 通りで、1\le k\le16で21523360
      • それにビット集合の演算が加わるが高々16ビットなので間に合う

こんなの書いたけど

inline int make_pq(int p, int q, int n) {
    // pの立っているビット (n箇所あるはず)にq (下位nビット)をあてはめる
    int x = 0;
    for (int i=0,b=1,m=1; i<n; ++i,m<<=1) {
        while (!(p & b)) b <<= 1;
        if (q & m) x |= b;
        b <<= 1;
    }
    return x;
}

→AC
https://atcoder.jp/contests/dp/submissions/3962870 659ms

V - Subtree (100)

V - Subtree
あるノードが黒で、そこと繋がる範囲だけが黒な場合の数。
全方位DPなんだろうけどどうしたらいいか分からない
いや、メモ化再帰で答えが合うやつは書けるんだけどTLE出るし
https://atcoder.jp/contests/dp/submissions/3963654

W - Intervals (100)

W - Intervals
区間に対してボーナス/ペナルティがあってというやつ

X - Tower (100)

X - Tower
可能なsub塔をs_iが小さい順に見ていく?

Y - Grid 2 (100)

Y - Grid 2
座圧したら行けるのか?

Z - Frog 3 (100)

Z - Frog 3
N=2\times10^5なのでFrog 2の方法ではO(N^2)で死
TLにCHTというワードが出ているのだけれど何それ
CHT=Convex Hull Trick