APC001: B - Two Arrays
問題
解説
aの増分が大きいため、Yesとなる場合は大まかに考えて、aがbに追いつくような形になる。逆にaの方が大きいような場合、bはaに追いつけず、Noとなる。
「同時に行う」と強調されているが、これは題意としてであり、解法を考えるときは独立的に増加させるのが良い場合が多い。
まずは各項の値を大体合わせようと考える。 1. 数列aを数列bに向かって合わせ、各項について同じになるか丁度超えたところでストップする。 2. 次に数列bが変更後の数列aに合わせる。aは1ずつ増加させられ調整が効くため、この順に行う。
さて、それぞれの操作回数を比較する。 - 1の操作回数 < 2の操作回数 のとき、bはaに追いつけないためNoである。 - 操作回数が一致するとき、(a が 追い越した分は b が調整しているため) Yes である。 - 1の操作回数 > 2の操作回数のとき、増分の差の絶対値が1であるため、必ずYesとなる。
int main() { int N; cin >> N; vector<int64_t> a(N); cin >> a; vector<int64_t> b(N); cin >> b; int64_t acnt = 0; rep(i, a.size()) { if (a[i] < b[i]) { auto num = (b[i] - a[i] + 1) / 2; a[i] += 2LL * num; acnt += num; } } int64_t bcnt = 0; rep(i, b.size()) { if (b[i] < a[i]) { auto num = a[i] - b[i]; b[i] += num; bcnt += num; } } cout << (acnt >= bcnt ? "Yes\n" : "No\n"); }