競プロがんばりたい

Two Arrays

精進

AtCoder Petrozavodsk Contest 001-B "Two Arrays"

ACはしたけどあんまりわかっていない．
次の自分が解く時に期待()

提出コード
atcoder.jp

考察

asum := $a[]$ の総和
bsum := $b[]$ の総和
とします．

$a[i]$ を $+2$ し， $b[j]$ を $+1$ するとき，全体で見ればasumを $+2$ ，bsumを $+1$ することになります．
そして， $a[]とb[]$ が等しい数列ならばasum=bsumになる．

2つの数列が等しくなるまでに行う操作の回数をnumとすると，
asum + 2num = bsum + num
$\therefore$ num = bsum - asum
です．

このnumより操作回数が多いことはあり得ません．
num回以降の操作では， $a[]$ の方が一方的に増えていくためです．

次に，任意の $0 \leq i < N$ に対して， ${\rm min}(a[i], b[i$ )]が ${\rm max}(a[i], b[i])$ 以上になるために必要な操作の最小回数を数えます．
・ $a[i] < b[i]$ のとき， $\frac{{\rm ceil}(b[i]-a[i])}{2}$ 回
・ $a[i] > b[i]$ のとき， $a[i]-b[i]$ 回
の操作が最低限必要．

このいずれもがnum以下ならば良いらしい(?)
そして実は上の2つの条件の内，1つ目だけで十分らしい．
恐らく，
$a[i]$ を $+2$ ， $b[j]$ を $+1$ ， $\to$ $a[j]$ を $+2$ ， $b[j]$ を $+1$ とすれば．
この2つの操作後には $a[i]$ が $+2$ ， $a[j]$ が $+2$ ， $b[j]$ が $+2$ のようになって，結果としては $a[j], b[j]$ は変えずに $i$ 番目のみ変更することができることに関係していそう．

未来の私，頑張れよ...