\(X_i\) は \(B_i,C_i\) のいずれかから選ぶことになりますが、これは \(\sum_{i=1}^{N} X_i \) を考える上では \(0, \max\{B_i,C_i\} - \min\{B_i,C_i\}\) のいずれかから選ぶことと同じです。 \(B_i+C_i=A_i\) を満たす \(B_i,C_i\) に対する \(\max\{B_i,C_i\} - \min\{B_i,C_i\}\) としてありうる整数は \(A_i\) 以下の整数のうち、 \(A_i\) と偶奇が等しいものです。よって問題は以下のように言い換えられます。

$i=1,2,\dots,N$ に対し $0\leq D_i \leq A_i,\ D_i \equiv A_i\ (\bmod\ 2)$ を満たす $D=(D_1,D_2\dots,D_N)$ であって、$D_1,D_2,\dots,D_N$ からいくつか選んだ和が $\frac{1}{2} \sum_{i=1}^{N}D_i$ になりえないものが存在するか？

結論から述べると上記のような \(D\) が存在する必要十分条件は

• ある整数 \(i\) であって、\(A_1,A_2,\dots, A_N\) のうち、 \(A_i\) 未満の奇数の個数が \(A_i-1\) 未満であるものが存在する

です。この判定は \(A\) をソートすれば \(O(N\log N)\) で簡単にできます。以下では \(A_1 \leq A_2 \leq \dots \leq A_N\) が成り立つとしたうえでこのことの証明を行います。

[1] 必要性

任意の \(A_i\) に対し、\(A_1,A_2,\dots, A_N\) のうち、 \(A_i\) 未満の奇数の個数が \(A_i-1\) 以上である場合、どんな \(D\) に対しても \(D_i\) からいくつか選んだ和が \(\frac{1}{2} \sum_{i=1}^{N}D_i\) になるような選び方が存在することを示せばいいです。ここではより強い事実として、\(i=1,2,\dots,N\) に対し以下が成り立つことを示します。

• \(S=0,1,2,\dots,\sum_{j=1}^{i}D_j\) に対し、\(D_1,D_2,\dots,D_i\) からいくつか選んだ和が \(S\) になるような選び方が存在する

\(i=k\) に対し成り立つとき \(i=k+1\) に対し成り立つことを示します。\(i=k\) に対し成り立つとき、 \(D_1,D_2,\dots,D_{k+1}\) からいくつか選んで作れる和は \(0,1,2,\dots, \sum_{j=1}^{k}D_j\) と \(D_{k+1},D_{k+1}+1,D_{k+1}+2,\dots, \sum_{j=1}^{k+1}D_j\) なので、 \(D_{k+1} \leq \sum_{j=1}^{k}D_j+1\) であることが示せればいいです。 \(D_j \equiv A_j\ (\bmod\ 2)\) であることから右辺の最小値は ( \(A_1,A_2,\dots,A_k\) のうち奇数の個数 ) \(+1\) であり、左辺の最大値は明らかに \(A_{k+1}\) であるため、\(A_{k+1} \leq \) ( \(A_1,A_2,\dots,A_k\) のうち奇数の個数 ) \(+1\) が示せればいいですが、これは最初に述べた必要十分条件と同じです。

以上より必要性が示せました。

[2] 十分性

条件を満たす \(D\) を実際に構築することで十分性を示します。\(A_1,A_2,\dots,A_N\) のうち \(A_i\) 未満の奇数の個数が \(A_i-1\) 未満の \(A_i\) のうち最小のものを \(a\) とします。

[2-1] \(a\) が奇数の場合

\(A_i\) が偶数のとき、 \(D_i=0\) 、 \(A_i\) が奇数かつ \(a\) 未満のとき、 \(D_i=1\) 、それ以外のとき、 \(D_i=a\) とします。ただし、この構築で \(D_i=1\) を満たす\(i\) の個数が偶数個になった場合は \(D_i=a\) を満たす \(i\) のうち \(1\) つだけ \(D_i=1\) とします。例えば \(A=(3,3,3,3)\) の場合、 \(D=(3,3,3,3)\) ではなく \(D=(1,3,3,3)\) とします。

このように構築した \(D\) が条件を満たすことを確認します。 \(D\) に含まれる \(1,a\) の個数はそれぞれ奇数であり、 \(2n+1,2m+1\ (2n+1 < a-1)\) とすると、 \(\frac{2n+1+a}{2}+am\) が作れないことを示せばいいです。

\(D_i\) からいくつか選んで作った和について、 \(a\) で割った余りは \(2n+1 < a-1\) より \(2n+1\) 以下です。一方目標の和である \(\frac{2n+1+a}{2}+am\) を \(a\) で割った余りは \(2n+1 < a-1\) より \(\frac{2n+1+a}{2}\) であり、これは \(2n+1\) より大きいです。よって \(\frac{1}{2} \sum_{i=1}^N D_i\) を作ることはできず、 \(D\) は条件を満たします。

[2-2] \(a\) が偶数の場合

\(A_i\) に \(a\) より大きい奇数が存在する場合、そのような奇数のうち最小のものをとれば [2-1] の方法で構築できます。そうでない場合、\(A_i\) が奇数の場合 \(D_i=1\) 、 \(A_i\) が \(a\) でない偶数の場合 \(D_i=0\) とし、 \(A_i=a\) となる \(i\) に対しては \(1\) つだけ \(D_i=a\) とし、それ以外について \(D_i=0\) とすると [2-1] と同様の議論で \(D\) が条件を満たすことを示せます。