はまやんはまやんはまやん

hamayanhamayan's blog

Two Arrays [AtCoder Petrozavodsk Contest 001 B]

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

解法

https://beta.atcoder.jp/contests/apc001/submissions/2064606

(i,i)で操作をすればA[i]+2、B[i]+1で相対的にA[i]++と出来るため、A[i]≦B[i]の場合は特に問題ではない。
難しいのはA[i]>B[i]の場合である。
この場合では(j,i)として、jは+2してもB[j]を上回らない様なjを選ぶ必要がある。
この操作を特殊操作と呼んでおこう。
この回数を数え上げながら判定していこう。
 
cnt := 特殊操作できる回数
A[i]<B[i]の場合は、+2できるチャンス。
floor((B[i]-A[i])/2)回だけ特殊操作する余裕があるため、これをcntに足す。
A[i]>B[i]の場合は、特殊操作をしてA[i] == B[i]とする必要がある。
特殊操作する必要がある回数は(A[i] - B[i])回なので、cntからこれを引く。
 
最終的に0≦cntであれば特殊操作は全て行えるので、Yes
負であれば、行えないのでNo

int N, A[10101], B[10101];
//---------------------------------------------------------------------------------------------------
#define yes "Yes"
#define no "No"
string solve() {
    ll cnt = 0;
    rep(i, 0, N) {
        if (A[i] < B[i]) {
            cnt += (B[i] - A[i]) / 2;
        } else {
            cnt -= A[i] - B[i];
        }
    }
 
    if (cnt < 0) return no;
    return yes;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) cin >> B[i];
    cout << solve() << endl;
}