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\) 回上のような操作ができないので、目的が達成できない。