AtCoder ABC 141 C - Attack Survival (灰色, 300 点)

ちょっと視点を変える感じ。
「反対側とか補集合とか余事象とか考えてみると解ける」という感じの問題は、300 点あたりからよく出てくる

問題へのリンク

問題概要

人がいてそれぞれ ポイントずつもっている。
これから ラウンドのクイズがあって、 ラウンド目には 人目が正解して、 人目以外のポイントが 1 ずつ減少する。

すべてのラウンドを終えたときに、各メンバーのポイントが 1 以上残っているかどうかを判定せよ。

制約

• 
• 
• 

考えたこと

いわゆるシミュレーション系の問題。
しかし愚直にやると

• 毎回の操作は 人のポイントを 1 ずつ減らすので
• 操作回数は 回

ということで全部で の計算量がかかってしまう。これでは間に合わない。

そこで見方を変えて、

• num[ i ] := i 人目が何問正解するか

を求めていくことにする。これなら毎回の操作で num[ A[ i ] ]++ という感じに 1 箇所変更するだけなので でできるようになる。これを求めておくと、最終的な得点は

• points[ i ] = K - (Q - num[ i ])

と求めることができる (Q 問中 num[ i ] 問正解なら、ポイント減少分は Q - num[ i ])。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, K, Q; cin >> N >> K >> Q;
    vector<int> num(N, 0);
    for (int i = 0; i < Q; ++i) {
        int a; cin >> a; --a;
        num[a]++;
    }

    for (int i = 0; i < N; ++i) {
        if (K - (Q - num[i]) <= 0) cout << "No" << endl;
        else cout << "Yes" << endl;
    }
}