AtCoder APC 001 B - Two Arrays

https://atcoder.jp/contests/apc001/tasks/apc001_b

$c_i = a_i - b_i$ とする。

3
1 2 3
5 2 2

であれば $c = [-4,0,1]$ となる。 目的は、全ての $i$ に対して $c_i = 0$ とすること。

$a_i$ に $2$ を足し、$b_i$ に $1$ を足す操作は、$i=j$ であれば $c_i$ に $1$ を足し(操作1とする）、 $i \neq j$ ならば $c_i$ に $2$ を足し、$c_j$ から $1$ を引く操作(操作2とする)に対応する。 数字を減らすのは操作2でしか行えないことに注意。

$c_i$ を非負の部分と負の部分に分け、 $I_+ = \{ i \mid c_i ≥ 0\}, I_- = \{ i \mid c_i < 0 \}$, $S = \sum_{i \in I+} c_i, V = \sum_{i \in I-}\lfloor |c_i|/2 \rfloor$ とおく。

$S$ は、操作2を行わなくてはいけない最低回数、$V$ は $0$ を超えないようにマイナスになっている $c_i$ に $2$ を足すことのできる最大回数とも考えられる。

操作1で任意の場所の数字を任意の数だけ増やせるので、$I_+ = \empty$ つまり $S=0$ の状態にできれば良い。

操作1 または 操作2 で $S$ を減らすことを考える。

操作2で、$c_i \le -2, c_j > 0$ となっている $i,j$ を選んで $c_i$ に $+2$, $c_j$ に $-1$ すること(操作☆と呼ぶ)でしか $S$ は減らせないことがわかる。 この時、$S, V$ がともに1減少する。

それ以外のパターンを考えると、

• 操作1 -> $c_i \ge 0$ なら $S$ が1増加、それ以外なら $V$ が0または1減少
• 操作2 -> $+2$ する操作により、 $S$ が 1以上増加するか $V$ が1減少する。$c_j \le 0$ の時、$-1$ する操作では $V$ を高々1しか増やせない。

上により、どう頑張っても $V$ を増やすことはできないことがわかる。

$S ≤ V$ ならば、$c_i \le -2, c_j > 0$ となっている $i,j$ を選んで操作☆を続けることで $S=0$ とできる。 それ以外ならどう頑張っても $S$ 回上のような操作ができないので、目的が達成できない。

https://atcoder.jp/contests/apc001/submissions/32369370