KEYENCE Programming Contest 2019：C - Exam and Wizard

atcoder.jp

方針

まず と の総和をそれぞれ計算します。前者が後者より小さいとき、どのように準備度を分配しても不合格になる試験が出てくるので、-1 を出力します。それ以外のときは、上手く準備度を分配すれば全ての試験に合格できます。

次に とします。 の試験は準備度が不足しており、の試験は過剰です。 の試験が一つもないとき、準備度は全ての試験で足りているので分配の必要はありません。 0 を出力します。

最後に、準備度が不足した試験がある場合を考えます。準備度を過剰な試験から不足している試験へと移動するわけですが、準備度を変更する試験の数を出来るだけ減らしたいので、最も過剰な問題から順番に移動元としていけばよいです。ここで不足分についてはその合計だけわかればよく、問題毎にどれだけ不足しているかという情報は不要です。他方で過剰分は問題毎に管理しておく必要があります。なぜなら準備度が不足している問題は必ず準備度の分配を受けるのに対し、過剰な問題については、必ずしも準備度を変更する必要がないからです。

実装においては、 なる の和の絶対値を として持っておきます。また をソートしておきます。そして i = N から順に準備度の移動元としていき、以下を繰り返して行けばよいです。

• のとき、その問題の過剰な準備度を全て不足分に回し( とし)、 次の問題へ移ります ()。
• のとき、その問題の過剰な準備度を不足分に回せば、全ての試験に合格できるようになります。

答えは、( となる問題の数) + ( で、かつ上の方法で準備度を分配することになった問題の数) で求まります。

ソースコード

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

int main(){
    int N;  cin >> N;
    vector<ll> A(N+1), B(N+1);
    ll sumA = 0, sumB = 0;
    for(int i=1; i<=N; i++){ cin >> A[i]; sumA += A[i]; }
    for(int i=1; i<=N; i++){ cin >> B[i]; sumB += B[i]; }
    if(sumA < sumB){
        cout << -1 << endl;
        return 0;
    }

    vector<ll> D(N+1);
    int ans = 0;
    ll S = 0; // 不足分の準備度の和(の絶対値)
    for(int i=1; i<=N; i++){
        D[i] = A[i] - B[i];
        if(D[i]<0){
            S += abs(D[i]);
            ans++; // D[i] < 0 の試験の数を数える
        }
    }
    if(ans == 0){ //  D[i] < 0 の試験が無いとき分配の必要はない
        cout << 0 << endl;
        return 0;
    }

    sort(D.begin(), D.end());
    for(int i=N; i>=1; i--){
        if(S > D[i]){
            ans++;
            S -= D[i];
        }else{
            ans++;
            break;
        }
    }
    cout << ans << endl;
}