[AtCoder] AtCoder Petrozavodsk Contest 001 B – Two Arrays
問題
https://atcoder.jp/contests/apc001/tasks/apc001_b方針
\( a_i \leq b_i\) のとき
\( b_i – a_i \) 回 \( a_i \) と \( b_i \) に操作を施します。
\( b_i < a_i\) のとき
\( a_i – b_i \) 回 \( b_i \) に1を加算することで、\( a_i = b_i \) となります。このとき、\( a_j \leq b_j – 2 \) となる \(a_j\) に \( 2 \) を\( a_i – b_i \) 回加算する必要があります。したがって、まず初めに、\( b_i < a_i\) となる要素に対して、
\[ t = \displaystyle \sum_{ i = 1 }^{ n } (a_i – b_i )\]
を計算します。\( t\) 回分 \( a_j \leq b_j – 2 \) となる \(a_j\) に対して \( 2 \) を加算することができれば同じ数列を作成できます。つぎに、\( a_i < b_i\) となる要素に対して、
\[ s = \displaystyle \sum_{ i = 1 }^{ n } \lfloor \dfrac{b_i – a_i}{2} \rfloor \]
を計算します。\( t \leq s \) となれば同じ数列を作成できます。
https://atcoder.jp/contests/apc001/submissions/3902653