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

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

AtCoder ABC 141 C - Attack Survival (300 点)

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

問題へのリンク

問題概要

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

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

制約

  •  2 \le N \le 10^{5}
  •  1 \le Q \le 10^{5}
  •  1 \le K \le 10^{9}

考えたこと

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

  • 毎回の操作は  N-1 人のポイントを 1 ずつ減らすので  O(N)
  • 操作回数は  Q

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

そこで見方を変えて、

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

を求めていくことにする。これなら毎回の操作で num[ A[ i ] ]++ という感じに 1 箇所変更するだけなので  O(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;
    }
}