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

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

2020-03-16

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

AtCoder AtCoder300点数列操作 Yes/No判定問題操作を好きな回数だけ行える SをTにすることが目的の操作の問題必要条件を列挙したら十分条件になる決めてから整合性を確認する Greedy:端から順に決まっていく Greedy 緑色diff AGC-like

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

問題へのリンク

問題概要

長さ $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;
}