APC001: B - Two Arrays

問題

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