同じ \(i\) を \(2\) 度選択すると元に戻るので, どの \(i\) も \(1\) 度選択されるか \(1\) 度も選択されないかのどちらかである.

選択した \(i\) の集合を \(G\) とすると, 総和 \(S\) は

\[S = \sum_{i=1}^N A_i - 2\sum_{i \in G} A_i\]

となり, 第一項は \(G\) に依らないので一定であり, 結局のところ第二項の \(\sum\) 部分だけに依る. すなわち, 問題は

\(K\) 個以下の \(A_i\) を選択したときの総和の種類を求めよ

と言い換えられる.

総和の最小値は \(1\) つも選択しない \(0\) であり, 総和の最大値は \(N-K+1\) から \(N\) までの和である. この間の数値はすべて作ることができる.

ある集合 \(G\) によって総和 \(M\) が作れているとき, 総和 \(M-1\) を作るためには次のようにすればいい.

  • \(G\) に \(1\) が含まれているなら \(G\) から \(1\) を取り除く.
  • そうでなければ, \(G\) の最小の要素をそれより \(1\) つ小さい要素に置き換える.

よって, 作ることができる総和の種類は,

\[\sum_{i=N-K+1}^N i + 1 = \frac{N(N+1)}{2} - \frac{(N-K)(N-K+1)}{2} + 1\]

である.