Educational DP Contest S,T,U,Vメモ

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

S - Digit Sum

• 1以上 $N$ 以下の整数で、各桁の和が $D$ の倍数であるものはいくつあるか
• $1 \le N \le 10^{10000}$
• $1 \le D \le 100$

桁DPと呼ばれるらしい。

ある数以下の整数を対象とするとき、上の桁から見ていって、境界ギリギリかどうかによって取り得る値の範囲が変わる。

例えば、$N=4567$とする。

• 最上位桁が0～3: 次の桁以降、どんな数字が来ても $N$ 以下
• 最上位桁が4: 次の桁の数字次第（下の分岐へ）
• 最上位桁が5～: 次の桁以降、どんな数字が来てもNG（考慮しなくてよい）

• 上位2桁が40～44: 次の桁以降、どんな数字が来ても $N$ 以下
• 上位2桁が45: 次の桁の数字次第（下の分岐へ）
• 上位2桁が46～: （考慮しなくてよい）

• 上位3桁が450～455: 次の桁以降、どんな数字が来ても $N$ 以下
• 上位3桁が456: 次の桁の数字次第
• 上位3桁が457～: （考慮しなくてよい）

次の桁の範囲が限られるか、自由かで、分けて状態を持つ。

桁DPでよく出てくる構造は、以下。

$DP[i][j][k]=$上位 $i$ 桁まで考慮して、次の桁の範囲は $[j=0:限られない/1:限られる]$ で、桁和の合計(mod D) が $k$ である数字の個数

ただ今回は単純なので、こんなんでもいい。

$DP[i][k]=$上位 $i$ 桁まで考慮して、次の桁の範囲が限られないもので、桁和の合計(mod D) が $k$ である数字の個数
$DP2[i]=$ 上位 $i$ 桁までの $N$ の桁和(mod D)

M - Candies と同じく範囲加算が必要なので、累積和を用いる。数字の範囲が「自由」か「制限」かで分類する。

$i$ 桁目は0～9の任意の値を取る。

$DP[i-1][s]=c$（$i-1$ 桁目までの和が $s$ のものが $c$ 個ある）時、愚直にやると

DP[i][s+0 mod D] += c
DP[i][s+1 mod D] += c
DP[i][s+2 mod D] += c
...
DP[i][s+9 mod D] += c

となる。遅いので、いもす法を使って高速化する。（累積和を取るのは後で）

DP'[s+ 0] += c
DP'[s+10] -= c

これを各 $s=0..(D-1)$ について行う。

$i-1$ 桁目までが $N$ と一致し、$i$ 桁目が $N_i$（Nのi桁目の数字）より小さいような数が、これになる。

$i-1$ 桁目までのパターン数は（$N$ と一致してないといけないので）当然1通り。その桁和をsとして、遷移は

DP[i][s+0 mod D] += 1
DP[i][s+1 mod D] += 1
...
DP[i][s+(Ni-1) mod D] += 1

となる。上と同様に累積和を使う。

DP'[s+0] += 1
DP'[s+Ni] -= 1

ここまでの各sについて処理後、DP[i] = DP'の累積和 として、遷移が完了する。

$i-1$ 桁目までが $N$ と一致し、$i$ 桁目も $N_i$ と一致する数が、これになる。

パターン数は1通りとわかっているのでDP配列に状態数を管理する必要は無い。 上記の「制限→自由」の際の更新に用いるので桁和だけ更新しておく。

$DP2[i]=DP2[i-1] + N_i % D$

DP配列における桁和の状態数は、mod D をとるため本来は $D$ 個（0～(D-1)）でいいのだが、 累積和による更新をやりやすくするため配列としては $D+10$ の大きさのものを作り、D以上の部分は累積和を取った後に移動させる。

最終的な答えは $DP[Nの桁数][0]$ だが、これには0も入っている。「1以上 $N$ 以下の整数」の個数を求めるので、1引く。

また、$N$ そのものは最後までDP配列で管理されないので、もし $N$ の桁和が $D$ の倍数だった場合は1足す。

P - Permutation

• 整数 $N$ と、'>'または'<'からなる $N-1$ 文字の文字列 $S$ が与えられる
• $\{1,2,...,N\}$ を並べ替えた順列 $\{p_1,p_2,...,p_N\}$ を考える
• 全ての $i=1～N-1$ について以下の条件を満たす順列の個数を $\mod 10^9+7$ で求めよ
  • $S$ の $i$ 文字目が '>' だった場合、$p_i \gt p_{i+1}$
  • $S$ の $i$ 文字目が '<' だった場合、$p_i \lt p_{i+1}$
• $1 \le N \le 3000$

N = 4   S = <><

1 < 3 > 2 < 4
3 < 4 > 1 < 2  など5個が条件を満たす

DP自体は割と普通だが、持たせる情報に「なるほど」という発想が必要。

まず愚直な思いつきが、

$DP[i][j][S]=i$ 番目の数字まで確定し、$p_i=j$ であり、未使用の整数の組が $S$ であるような状態の数

必要な情報を考えると、次に来る数字を決めるに当たって前の数字（$p_i$）は必要だし、 $p_i$ が同じでも残る整数の組によって次に来れる数の個数は異なってくる。

だが、これはどう考えても $S$ が管理できる状態数にならない。

次のようにすると良いらしい。

$DP[i][j]=i$ 番目の数字まで確定し、$p_i$ が、($p_i$を含めた)残る整数の中で $j$ 番目に小さいものであるような状態の数

各項が全て異なる数列の、隣り合う数字の大小を考慮するだけなら、数字の順位のみが重要となる。

• 「1,2,3,4,5」から
  • 既に2,4が使われていて、「1,3,5」の中から3を選び、残りが「1,5」
  • 既に3,5が使われていて、「1,2,4」の中から2を選び、残りが「1,4」

の2つは、その後の状態数は全く同じになるため、区別する必要が無い。

$k=N-i$（$i$を含めない残りの数字の個数）とする。また、数字の順位を0-indexとする。

• $DP[i][0]$ からは、$DP[i+1][0]～DP[i+1][k-1]$ のそれぞれに遷移できる
• $DP[i][1]$ からは、$DP[i+1][1]～DP[i+1][k-1]$ のそれぞれに遷移できる
• $DP[i][k-1]$ からは、$DP[i+1][k-1]$ にのみ遷移できる
• $DP[i][k]$ からは、どこにも遷移できない
• 遷移した時点で数字が1個減っていることに留意
• すると、これは単に累積和である

  k|  9
k-1|  7    1+3+5+..7
   |       ...
  2|  5    1+3+5
  1|  3    1+3
  0|  1    1
---+------------------
      i     i+1

• $DP[i][k]$ からは、$DP[i+1][0]～DP[i+1][k-1]$ のそれぞれに遷移できる
• $DP[i][k-1]$ からは、$DP[i+1][0]～DP[i+1][k-2]$ のそれぞれに遷移できる
• $DP[i][1]$ からは、$DP[i+1][0]$ にのみ遷移できる
• $DP[i][0]$ からは、どこにも遷移できない
• すると、これは逆向きの累積和である

  k|  9
k-1|  7    9
   |       ...
  2|  5    9+7+..
  1|  3    9+7+..+5
  0|  1    9+7+..+5+3
---+------------------
      i     i+1

最終的に $DP[N]$ の長さは1になるので、$DP[N][0]$ が答え。

U - Grouping

• ウサギが $N$ 匹
• 各ウサギ同士の相性は $a_{i,j}$ で行列の形で与えられる（負もある）
• ウサギをグループ分けする
  • 各ウサギは、丁度1つのグループに属する
  • グループの個数は問わない
• ウサギ $i$ と $j$ が同じグループに属すると、スコア $a_{i,j}$ を得る
• 上手くグループ分けしてスコアを最大化せよ
• $1 \le N \le 16$
• $1 \le |a_i| \le 10^9$
• $a_{i,i}=0, a_{i,j}=a_{j,i}$

bitDP

$SG[s]=$集合 $s$ に属するウサギが全て同一グループに入る時のスコア

$DP[s]=$集合 $s$ に属するウサギだけでグループ分けして得られる最大スコア

$SG$ は、事前計算する。

たとえば $s=0011010$ の時、最下位で立っているビット(2) とそれ以外(4,5) に分けて考えると、$SG[0011010] = SG[0011000] + a_{2,4} + a_{2,5}$ のように計算できる。

$DP$ の計算が肝。

$s$ の部分集合 $p$ を全探索する。$p$ を同一グループに入れ、残り（$s \setminus p$）の最適な分け方はそれより前に計算したDPの値を参照し、その合計の最大が $DP[s]$ となる。

$\displaystyle DP[s]=\max_{p \subseteq s}(SG[p]+DP[s \setminus p])$

$s$ の部分集合 $p$ はどのように得たらいいか。愚直に $0～2^N$ を回して $s$ の部分集合か1つずつ確かめるのはさすがにTLE。

減算とマスクを用いると、上手く全ての部分集合を得られる。

• ビット列による部分集合表現 【ビット演算テクニック Advent Calendar 2016 1日目】 - prime's diary

g = h = 0b011010
while h:
    print(f'{h:06b}')
    h = (h - 1) & g
# =>
# 011010
# 011000
# 010010
# 010000
# 001010
# 001000
# 000010

$s$ の小さい方から $DP$ を埋めていき、$s=2^N-1$ の時が答え。

V - Subtree

• 頂点数 $N$ の木の各頂点を、白か黒で塗る
• 黒の頂点は連結でないといけない
• 各頂点 $v$ について、$v$ を黒く塗ったときの塗り方のパターン数を求めよ
• 答えは、$M$ で割った余りで答えよ
• $1 \le N \le 10^5$
• $2 \le M \le 10^9$

全方位木DPと呼ばれるらしい。

木DPは適当な1頂点を根とするが、全方位木DPは、全ての頂点を根として考えなければならない場合に使う(と思う)

まずは普通に適当な頂点を根としてDFSなどで木DPする。

その後、2回目のDFSを行う。 親から頂点 $v$ に移動するとき、「$v$ が根になった場合の答えを求めるのに必要な情報」を与えながら移動する。 この値は根から累積的に計算できるようにしておく。

• †全方位木DP†について - ei1333の日記
• もうひとつの全方位木DP - ei1333の日記

$DP1[v]=$（頂点1を根として）頂点 $v$ 以下の部分木で、$v$ を黒く塗るようなパターン数

探索方法は何でもよいが、頂点1から再帰的にDFSで求めるとする。

頂点 $v$ の子の1つを$u$とする。

• $u$ が黒かったら$DP1[u]$通り。
• $u$ が白かったら$u$以下の部分木は全て白く塗るしか無いので、1通り。

計$DP1[u]+1$通りの塗り分け方が、$u$ 以下の部分木に対して可能である。同様に$v$の各子供に対して求め、掛け合わせた数が、$DP1[v]$となる。

$\displaystyle DP1[v] = \prod_{u \in vの子供} (DP1[u]+1)$

$v=1$ の時の出力すべき答えは、最終的な $DP1[1]$ に入っている。根が指定されていればこれで良かった。

同様にDFSで頂点1から探索するとする。

頂点 $v$ の親を $p$ とする。

また「もし親子関係が逆転して、$p$ が $v$ の子になったら、$p$ 以下の部分木を塗り分けるパターン数$a$」が $p$ から伝えられているとする。

2回目の遷移では、以下のことを行いたい。

• 部分木ではなく、木全体での $v$ を黒く塗るときのパターン数（つまり出力すべき答え）を求める
• 各子供 $u$ に、「もし $v$ が $u$ の子になったら、$v$ 以下の部分木を塗り分けるパターン数」を伝える

1つめは簡単で、$DP1[v] \times a$ がそれになる。 要は$DP1$では、$v$から伸びる枝のうち $p$ に伸びるもののパターン数だけが考慮できてなかったのが、 $p$から伝えられたので、情報が補完された。

2つめは、少し厄介。 率直には「$v$ から伸びる枝のうち $u$ に伸びるものだけを掛け合わせないパターン数」を伝えれば良い。

$\displaystyle \frac{DP1[v] \times a}{DP1[u]+1}$ をすればよい……かと思うが、値はとても大きくなるため、$M$ で割った値が入っている。 しかし、この $M$ はいつものように素数とは限らないため、モジュラ逆数が使えない。要は割り算が出来ない。

ならば、$a \times \prod_{c \in vの子供\setminus\{u\}} (DP1[c]+1)$ のように、$u$を除いた子のDP1の値を逐一かけてもよいが、 $v$ にめっちゃ多くの子がぶら下がっていた場合、全ての子でやると $O(子の数^2)$ の計算量が必要となり、特殊な入力でTLEする。

このように、割り算が出来ない状況下で「ある集合から、1つだけを除いた積」を求めたい場合は、前後双方からの累積積を求めておくと良い。

      i        1    2    3   4    5
      v        2    3    5   7   11
      ----------------------------------
累積積pf  1    2    6   30 210 2310
累積積pb    2310 1155  385  77   11    1

前後の'1'は計算上の便宜的なものとする。 $i=3$ を除いた積を求めたい場合は、pf[2] と pb[4] を掛け合わせればよい。6×77=462となる。 （実際のindexは異なるが、イメージとして）

各頂点についての子の累積積は、1回目の探索の際についでに求めたが、2回目の探索時にその頂点についてだけ構築した方がメモリに優しいね。

これで、$u$に、$v$ が部分木となった場合のパターン数を伝えられ、連鎖的に全頂点の答えが求められた。