読者です 読者をやめる 読者になる 読者になる

問題解決の宝石箱

競技プログラミング/数学ネタ置き場

Wunder Fund 2016-F : Double Knapsack

2016年 Codeforces ☆7 数学 解を一つ出力

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

問題

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

解答コード

差が  {D} であったときの A と B の位置を配列に覚えておき、しゃくとり法の要領で実装した。

gist55cdb08a1a9b0ff361eeb358669214f9