APC001 B - Two Arrays

問題ページ
B - Two Arrays

考えたこと

• 考えるのはa[i]とb[i]の差だけでよい
• a[i] < b[i] だとすれば a[i]+2, b[i]+1とすれば差が1縮まるので周りの状況にかかわらず絶対に等しく出来る
• a[i] > b[i] のときは a[j]+2, b[i]+1 (a[j] < b[j]) とする必要がある
• a[i] > b[i] で b[i] を大きくするのに必要な分a[j] < b[j]となっている部分があるか判定すればよい

300にしては難しくない？

#include "bits/stdc++.h"

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define PB push_back

const ll LLINF = (1LL << 60);
const int INF = (1LL << 30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> T ceil(T a, T b) { return a / b + !!(a%b); }
template<class S, class T>
ostream &operator <<(ostream& out, const pair<S, T>& a) {
    out << '(' << a.first << ',' << a.second << ')';
    return out;
}
template<class T>
ostream &operator <<(ostream& out, const vector<T>& a) {
    out << '[';
    REP(i, a.size()) { out << a[i]; if (i != a.size() - 1)out << ','; }
    out << ']';
    return out;
}

int dx[] = { 0, 1, 0, -1 }, dy[] = { 1, 0, -1, 0 };

signed main(void) {
    int n;
    cin >> n;
    VI a(n), b(n);
    REP(i, n) cin >> a[i];
    REP(i, n) cin >> b[i];

    VI v1, v2;
    REP(i, n) {
        if (a[i] > b[i]) {
            v2.push_back(a[i] - b[i]);
        }
        else if (a[i] < b[i]) {
            v1.push_back(b[i] - a[i]);
        }
    }

    int idx = 0;
    for (int &i : v2) {
        // 2*i点分
        while (idx < v1.size() && i > 0) {
            if (v1[idx] >= i*2) {
                v1[idx] -= i*2;
                i = 0;
            }
            else {
                i -= v1[idx]/2;
                v1[idx++] %= 2;
            }
        }
    }

    for (int i : v2) {
        if (i != 0) {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;

    return 0;
}