UNICORNプログラミングコンテスト2022(AtCoder Beginner Contest 269) G,Ex問題メモ

UNICORNプログラミングコンテスト2022(AtCoder Beginner Contest 269)

G - Reversible Cards 2

• $N$ 枚のカードがあり、それぞれ表に $A_i$、裏に $B_i$ の整数が書かれている
• $\sum_{i=1}^{N}(A_i+B_i)=M$ として、$k=0,1,2,...,M$ について、以下の答えを求めよ
  • はじめ、全て表が上になっている
  • 上になっている面に書かれた整数の和をちょうど $k$ にするために、裏返す必要がある枚数の最小値を求めよ
  • どうやっても不可能なら -1 を出力せよ
• $1 \le N \le 2 \times 10^5$
• $1 \le M \le 2 \times 10^5$
• $0 \le A_i,B_i \le M$

$S=\sum A_i$ とする。これが初期状態で上になっている面に書かれた整数の和である。
$D_i=B_i-A_i$ とする。カード $i$ を裏返すと、これだけ総和が増減する。

以下のナップサック（負の価値がありえるver.）をすると答えが求まるが、$O(NM)$ のためTLEとなる。

• $DP_{(仮)}[i,j]=i$ 枚目のカードまで考慮して、総和を $j$ にするために裏返す必要のある枚数の最小値

高速化したい。ここで、以下の性質を利用できる。

• $D_i$ には、同じ値がいっぱい含まれやすい
• → $D_i$ が同じものは、なるべくまとめて遷移する

$D_i$ の「種類数」をなるべく多くするようなテストケースを考えると、 $(A_i,B_i)=(0,1),(1,0),(0,2),(2,0),(0,3),(3,0),...$ のようなものがある。
（※(0,0)はいくらでも増やせるし、意味が無いので省略）

このとき $D_i=1,-1,2,-2,3,-3,...$ であり、$A_i+B_i=|D_i|$、$\sum_i(A_i+B_i)=M \le 2 \times 10^5$ である。
制約内で、$|D_i|=t$ となるところまで作れるとして、$M \ge \dfrac{t(t+1)}{2} \times 2$ となる。
$t \lt \sqrt{M}$ であり、種類数は $O(\sqrt{M})$ となる。

次に、$D_i$ が同じものをまとめて遷移させる方法を考える。$D_i=d$ となる $i$ が $x_d$ 個あったとする。

同じ品物が複数個あるナップサック問題のテクニックとして、2の冪乗のグループを作るというものがある。
$x_d=1+2+4+8+...+2^k+端数$ と分解し、それぞれの個数分をまとめた $log{x_d}$ 個のグループに分ける。

すると、$1～x_d$ のどのような値もいくつかのグループの組合せで実現でき、遷移回数を $O(\log{x_d})$ まで落とせる。

こうすることで計算量は、単純な見積もりで $O(M \sqrt{M} \log{M})$ となる。
実際には「$M$ の種類数」と「$D_i$ が同じものの個数の多さ」はトレードオフの関係にあるので、より少なくなる。

ちゃんとした計算量見積もりは公式Editorial参照。$O(N+M^{1.5})$ となるらしい。

• 解説 - UNICORNプログラミングコンテスト2022(AtCoder Beginner Contest 269)

Python3

Ex - Antichain

• $N$ 頂点の、頂点1を根とした根付き木が与えられる
• $k=1,2,...,N$ について、以下の条件を満たす頂点集合 $S$ の個数を $\mod{998244353}$ で求めよ
  • $|S|=k$
  • $S$ のどの2つの頂点 $u,v$ も、祖先-子孫関係にない
• $2 \le N \le 2 \times 10^5$
• 実行制限時間: 8sec.

以下の木DPを定義し、

• $DP_{(仮)}[v,k]=$ 頂点 $v$ 以下で、条件を満たすサイズ $k$ の頂点集合の個数

ある頂点から見て異なる子に属する頂点同士は、互いに影響しないので、それぞれ独立に自由に選べる。
よって子のDPの結果をFFTを使って合成していく、という解法が思いつくが、ムカデグラフのような場合に上手くいかない。

• Centipede Graph -- from Wolfram MathWorld

  ○
 ／＼         ← ③合成後サイズ N のFFT
○  ○
   ／＼       ← ②合成後サイズ N-2 のFFT
  ○  ○
     ／＼     ← ①合成後サイズ N-4 のFFT
    ○  ○
       ／＼    （丸付き数字は処理順）
       :  :

既にサイズが肥大化した配列を何度もFFTすることになってしまうので、$O(N^2)$ となる。

こういう時、DPの計算が結合法則を満たすなら、長いpathを分割統治できるHL分解が有効になる場合がある。

ある1つの Heavy-path を考える。各頂点にくっつくHeavy-path以外の頂点を、Light-children とする。

○--○--○--○--○--○--○--○    ←Heavy path
 |   |  |\   |   |   |   |
 ○  ○ ○○ ○  :   :   :        ←Light children
  `○    `○

以下を定義する。

• $DP_1[l,r,k]$
  • Heavy-path上の区間 $[l,r]$ 上の頂点の、Light-children以下の部分森からの、条件を満たす頂点集合の選び方の個数
• $DP_2[l,r,k]$
  • Heavy-path上の区間 $[l,r]$ 上の頂点の、Light-children以下の部分森および $[l,r]$ 上の頂点からの選び方の個数
  • ただし $[l,r]$ 上の頂点は必ず選ばれている

l           r
◎--◎--◎--◎--○--○--○--○  DP1[l,r]=●からの選び方
 |   |  |\   |   |   |   |      DP2[l,r]=●および◎からの選び方、ただし◎からは必ず選ぶ
 ●  ● ●● ●  ○  ○  ○
  `●    `●

こうすると結合法則が成り立ち、Heavy path上のDPを半分ずつ統合していくことができる。

l1          r1  l2          r2
◎--◎--◎--◎--○--○--○--○
 |   |   |   |   |   |   |
 :   :   :   :   :   :   :

DP1[l1,r2] = DP1[l1,r1] * DP1[l2,r2]
DP2[l1,r2] = DP1[l1,r1] * DP2[l2,r2] + DP2[l1,r1]

※ただし * は添字 k に対する畳み込み

Heavy-path の最左頂点を $L$、最右頂点を $R$ として、$DP[L] = DP1[L,R]+DP2[L,R]$ が、Heavy-path全体の結果となる。

この結果を $L$ の親に伝えれば、親の Heavy-path のDPを計算するのに必要な情報となる。

            P
○--○--○--○--○--○                 親のHeavy-path
 |   |   |  ↑↖
 :   :   :  │ ○--○--○--○--○--○  Light-child1のHeavy-path
            │ L1
            ○--○--○--○--○--○     Light-child2のHeavy-path
            L2

DP1[P,P] = DP[L1] * DP[L2] * ...（子の数だけ畳み込み）
DP2[P,P] = [0, 1]

DP1の畳み込みも、考えなくやると冒頭のムカデグラフと同様の問題が発生しうる。
要素数が小さい方から優先的におこなっていくことで、全体で $O(N \log{N})$ となる。

Heavy-path上の畳み込みも、隣り合った箇所のサイズが小さい方から上手くやると $O(N \log{N})$ になるらしいが、 順番を崩さないようにする必要があり難しいので、特に工夫せず2個ずつ統合していく実装でも、$O(N \log^2{N})$ となる。

実行制限時間が長いので、$O(N \log^2{N})$ でも間に合う。

Python3