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; }