C - Attack Survival

はじめに

たなしょです。

TLEをで回答ならずでした。 こちらのブログを参考にしています。

問題文

https://atcoder.jp/contests/abc141/tasks/abc141_c

考え方

配列numにn個の要素を持たせて、各要素の値は0にします。

vector<int> num(n, 0);

0からq未満まで正解者を入力します。 --aはnumの要素数に合わせているために実施している（オフセット始まりだから） 該当する要素に+1します。

for (int i = 0; i < q; ++i) {
    int a;
    cin >> a;
    --a;
    num[a]++;
}

++(q-num[i])++は正解数-配列iの要素の中身を求めることでi番目の人のマイナスポイントがわかります。 kポイント-i番目の人のマイナスポイントの減算が0以下ならNo、それ以外ならYesを出力します。

for (int i = 0; i < n; i++) {
    if(k-(q-num[i]) <= 0) {
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
    }
}

いざ実装

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <cmath>

typedef long long ll;

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;
        }
    }
}

最後に

TLEを改善するためにパフォーマンスも考える必要がありますね。

最後まで読んでいただいてありがとうございました。 もしよろしければtwitterアカウント（@piklus100yen）もフォローしていただけると幸いです！