AtCoder Beginner Contest 269 G問題 Reversible Cards 2

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

$N$ 枚のカードがある. $i$ 枚目の表には $A_i$ , 裏のカードには $B_i$ が書かれている. ここで, $\displaystyle \sum_{i=1}^N (A_i+B_i)=M$ が成り立つ.

このとき, $S=0,1,2, \dots, M$ について以下の問に答えよ.

$0$ 枚以上のカードを裏返すことによって, 見えている整数の和を $S$ にすることは可能か? 可能ならばその裏返すカードの最小枚数を答えよ.

制約

$1 \leq N \leq 2 \times 10^5$
$0 \leq M \leq 2 \times 10^5$
$0 \leq A_i, B_i \leq M$
$\displaystyle \sum_{i=1}^N (A_i+B_i)=M$

解法1

$i=1,2, \dots, N$ に対して, $D_i=B_i-A_i$ とする. また, $A_{{\rm sum}}:=A_1+\dots+A_N$ とすると, この問題は次の問題に帰着される.

$S=0,1,2, \dots, M$ について以下の問に答えよ.

$D_1, \dots, D_M$ から $0$ 個以上選び, その総和を $S-A_{{\rm sum}}$ にすることは可能か? 可能ならば選び出す整数の個数の最小値を求めよ.

これは愚直な動的計画法で解こうとすると, $\Omega(NM)$ 時間かかり, 間に合わない.

解法2

ここで, 一般的に以下が成り立つ.

$E=(E_1, \dots, E_N)$ を非負整数列とし, その総和を $M$ とする. このとき, $E$ に出てくる整数の種類の数は高々 $(\lfloor \sqrt{2M} \rfloor+1)$ である.

(証明)

$E$ に出てくる $0$ 以外の整数を昇順に $e_1, \dots, e_K$ とし, それぞれ $a_1, \dots, a_K$ 個であるとする.

このとき, $e_i \geq i, a_i \geq 1$ が成り立つので,

$\displaystyle M=\sum_{i=1}^K e_i a_i \geq \sum_{i=1}^K i=\dfrac{1}{2}K(K+1) \geq \dfrac{1}{2}K^2$

よって, $2M \geq K^2$ であるから, $\lfloor \sqrt{2M} \rfloor \geq K$ であるから, $E$ における $0$ の有無を考慮することにより, 高々 $(\lfloor \sqrt{2M} \rfloor+1)$ 種類であることがわかった.

また, $D$ について,

$\displaystyle \sum_{i=1}^N |D_i|=\sum_{i=1}^N |B_i-A_i| \leq \sum_{i=1}^N (|B_i|+|A_i|)=\sum_{i=1}^N (A_i+B_i)=M$

であるから, $D_i$ における正部分, 負部分それぞれについて考えることによって, $D$ に出てくる整数の種類の数は高々 $2 \times (\lfloor \sqrt{2M} \rfloor+1)$ であり, $O(\sqrt{M})$ 種類となることがわかった.

$D$ において, $D$ において $L$ 種類の整数が登場し, 整数 $d_j$ が $a_j~(a_j \geq 1)$ 個登場するとする. このとき, 考える問題は次のようにして帰着できる.

次のようなスコアとコストのペアがある. なお, スコア $s$ とコスト $c$ のペアを $(s,c)$ と書くことにする.

$(d_1, 1), (2 d_1, 2), \dots, (2^{t_1-1} d_1, 2^{t_1-1}), ( (a_1-(2^{t_1}-1) ) d_1, a_1-(2^{t_1}-1) )$
$\vdots$
$(d_L, 1), (2 d_L, 2), \dots, (2^{t_L-1} d_L, 2^{t_L-1}), ( (a_L-(2^{t_L}-1) ) d_L, a_1-(2^{t_L}-1) )$

これら $( (t_1+1)+\dots+(t_L+1) )$ 個のペアから $0$ 個以上のペアを選び, スコアの総和をちょうど $S-A_{{\rm sum}}$ にすることは可能か? 可能ならばコストの総和の最小値を求めよ. ただし, 各 $t_i$ は $a_i \geq 2^{t_i}-1$ を満たす最大の整数とする.

次のような動的計画法で解くことができる.

初期条件: ${\rm DP}[0,j ]$ は $j=0$ のとき $0$ , $j \neq 0$ のときは $+\infty$
更新式: $i$ 番目のペアを $(s_i, c_i)$ としたとき.

${\rm DP}[i,j]=\min ({\rm DP}[i-1, j], {\rm DP}[i-1, j-s_i]+c_i)$

この動的計画法によって, ペアの個数を $T$ としたとき, ${\rm DP}[T, S-A_{{\rm sum}} ]$ が答えである.

ここで, ペアの個数について, $t_i=O(\log a_i)=O(\log M)$ であるから, $D$ に出てくる整数の種類の数が $O(\sqrt{M})$ であることも合わせて, $T=O(\sqrt{M} \log M)$ である.

よって, $0 \leq S \leq M$ の範囲を答えることになっていおり, $0 \leq A_i, B_i \leq M, \displaystyle \sum_{i=1}^N (A_i+B_i)=M$ の制約から, 全体の計算量を $O(\sqrt{M} \log M \times M)=O(M^{3/2} \log M)$ 時間で求めることができた.