おそらく今年最後の記事。

問題

Wunder Fund 2016-F : Double Knapsack

【Wunder Fund 2016-F : Double Knapsack】

長さ $N$ の正の数列が 2 つ与えられる($A, B$ とおく)。
数列に含まれる数は 1 以上 $N$ 以下の整数である。
$A, B$ から空でない部分列をそれぞれ適当に選択したとき、合計が等しくなるようにできるだろうか？
もしできる場合は、具体的に構成せよ。できなければ、その旨を報告せよ。

$1 \leq N \leq 10^{6} $

ヒント：here

解説

鳩の巣原理を適用して、答えが必ず存在することが示せる。

以降、$A$ の先頭 $x$ 個の和を $SA_{x} = \sum_{i=1}^{x} A_{i} (0 \leq x \leq n) $、$B$ の先頭 $x$ 個の和を $SB_{x} = \sum_{i=1}^{x} B_{i} (0 \leq x \leq n) $ とおく。ただし、$SA_{N} \leq SB_{N}$ とする。（そうでない場合は $A$ と $B$ を入れ替える。）

鳩 := $ SA_{x} $ - $ SB_{y} $　ただし、各 $x$ に対して、値が負にならないような最大の ${y}$ のみを考える。つまり、Aの部分和から、Bの部分和を引けるだけ引く、ということ。これが各 $x$ に対して存在するので、鳩は N+1 羽。
巣 := ↑で示した部分和の差は 0 から N-1 までの値を取りうる。$SA_{x} - SB_{y} \geq N$ とすると、$y$ をいくつか増やして $SA_{x} - SB_{y+d} \leq N-1$ とできる。巣は N 個。

鳩の巣原理を適用すると、部分和の差が等しいような位置の組 $(x, y)$, $(x', y')$, $ D = SA_{x} - SB_{y} = SA_{x'} - SB_{y'} $ がある。このとき、$ x' > x $ ならば、 $ SA_{x'} - SA_{x} = SB_{y'} - SB_{y} > 0 $ なので、$y' > y$ である。

したがって、部分和の差が等しい位置の組に対して、それぞれ差分を取ると空でない $A$, $B$ の部分列が得られ、これらの和が等しくなる。以下は $N = 8$ の例。「部分和の差」の行の二段目に書かれている $(x, y)$ は、$A$ の先頭$x$個の和から、 $B$の先頭$y$個の和を引いたことを示している。

f:id:hama_DU:20161225024622p:plain