Codeforces Round #577 (Div. 2) B. Zero Array

お題箱より。

Problem - 1201B - Codeforces

問題概要

$n$ 個の正整数 $a_{1}, ..., a_{n}$ が与えられる。これに

異なる2つの要素を選び、それぞれの要素を1減らす。

という操作を繰り返すことで全ての要素を0にできるかどうか判定せよ。

制約

$2 \le n \le 10^{5}$
$1 \le a_{i} \le 10^{9}$

解法

この判定は競技プログラミングではしばしば登場し、もう少し難しい問題の考察の1過程として登場することもあります。必要十分条件は知識として覚えておく価値があります。

要素和 $S = \sum_{i=1}^{n}a_{i}$ とします。この問題の条件を満たす必要十分条件は

$S$ が偶数である。
$\max_{i} a_{i} \le \frac{S}{2}$ である。

これらを2つとも満たすことです。

必要性は理解しやすいと思います。もし合計が奇数だと2ずつ減らしていって0になることは絶対ありませんし、もし最大要素が合計の半分を超えていたら、その要素と他の要素を組めるだけ組んでも最大要素が余ってしまいます。

あとは十分性です。これを証明します。

十分性の証明1

良い証明がないかググってみたのですが見つからず…私が思いついたのは数学的帰納法です。合計値 $S$ が正の偶数であることは前提として、要素の最大値が $\frac{S}{2}$ 以下である全ての数列が問題の条件を満たすことを証明します。

まず $S = 2$ から始めます。合計値が2で最大値が1以下である正整数の数列としてあり得るのは $1, 1$ だけです。これは明らかに問題の条件を満たします。

次に「合計値が正の偶数 $s$ で最大値が $\frac{s}{2}$ 以下である全ての数列は問題の条件を満たす」という仮定のもとで、合計値が $s+2$ で最大値が $\frac{s+2}{2}$ 以下である全ての数列が問題の条件を満たすことを示します。

ここで、最大値を取っている（すなわち同率1位の）要素の個数で場合分けをします。

最大値を取っている要素が2個以下の場合、それらをペアに含めることで要素の最大値は必ず1減ります。この操作によって数列の合計値は $s$ 、最大値は $\frac{s+2}{2} - 1 = \frac{s}{2}$ 以下になります。
最大値を取っている要素が3個以上の場合、そもそもこの最大値は $\lfloor\frac{s+2}{3}\rfloor$ 以下であるはずです。全ての正の偶数 $s$ に対してこの値は $\frac{s}{2}$ 以下であることが不等式を評価することで示せるので、操作後の最大値も $\frac{s}{2}$ 以下です。

つまりどちらの場合でも、適切に操作をすると合計値が $s$ で最大値が $\frac{s}{2}$ 以下であるような数列にすることができて、帰納法の仮定よりこれは問題の条件を満たします。

十分性の証明2

十分性の証明で前に見かけたやつ(熨斗袋くんだったと思う)
例えば a1=2, a2=5, a_3=9, a4=3, a5=1 だとして、それぞれ必要な操作回数を sum/2 = 10列に以下のように並べて、縦に並んだ2個を操作すればOK
1122222333
3333334445
— てんぷら (@tempura_cpp) September 2, 2019