けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder Petrozavodsk Contest 001 B - Two Arrays (300 点)

面白かった。間違いやすいけど、このくらいなら!!!

問題へのリンク

問題概要

長さ  N の正の整数からなる二つの数列  a_{1}, \dots, a_{N} b_{1}, \dots, b_{N} が与えられる。以下の操作を好きな順序で好きな回数だけ行える。 a b が一致するようにすることは可能か?

  •  a の要素を一つ選んで  +2 する
  •  b の要素を一つ選んで  +1 する

制約

  •  N \le 10^{4}

考えたこと

とりあえず、 a の方が全体的に小さい必要がありそう。極端な話、すべての index について、a[ i ] <= b[ i ] であれば、全然可能である。

よって話は、a[ i ] > b[ i ] となっているような場所をいかにして補償するかである。

  • a[ i ] > b[ i ] のところについて、b[ i ] に 1 を足す代わりに
  • a[ j ] < b[ j ] のところについて、a[ j ] に 2 を足す

という風にしていく。その結果、すべての index について a[ i ] <= b[ i ] とにう状態になれば "Yes"、そうでなければ "No" だ。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N; cin >> N;
    vector<long long> a(N), b(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
    for (int i = 0; i < N; ++i) cin >> b[i];
    long long biggerA = 0, biggerB = 0;
    for (int i = 0; i < N; ++i) {
        if (a[i] > b[i]) biggerA += a[i] - b[i];
        if (b[i] > a[i]) biggerB += (b[i] - a[i])/2;
    }
    if (biggerB >= biggerA) cout << "Yes" << endl;
    else cout << "No" << endl;
}