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

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

AtCoder ABC 151 C - Welcome to AtCoder (300 点)

間違わないように、正確に、シミュレーションする問題。

問題へのリンク

問題概要

あるコンテストでは  N 問が出題される。それに対して  M 個の提出をした。提出結果はそれぞれ

  •  (p, s): 問題  p に対して、 s = "AC", "WA" のいずれかのフィードバックが得られる

というものである。この結果の「正答数」と「ペナルティ数 (正解した問題で AC するまでの WA の数の合計)」を求めよ。ただし、"AC" を出した問題に対してその後 "WA" を出してもペナルティとはならない。

制約

  •  1 \le N \le 10^{5}
  •  0 \le M \le 0^{5}
  •  1 \le p_{i} \le N

考えたこと

 p の値が小さいので、

  • wa[ p ] := 問題 p で何個 WA を出したか
  • isac[ p ] := 問題 p を正解できたかどうか

という配列を管理することができる。もし  p が大きかったり、文字列だったりした場合には std::map などの連想配列を使うとよさそう。

そして、「正答数」a と「ペナルティ」b は、以下を繰り返して求められる。

  • (p, WA) に対しては、 wa[ p ] をインクリメント
  • (p, AC) に対しては、
    • isac[ p ] = true のときは、何もしない
    • isac[ p ] = false のときは、++a して、b += wa[ p ] として、isac[ p ] = true にする
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, M; cin >> N >> M;
    long long ac = 0;
    long long pena = 0;
        
    vector<long long> wa(N, 0), isac(N, 0);
    for (int i = 0; i < M; ++i) {
        int p; string s;
        cin >> p >> s;
        --p;
        if (s == "AC") {
            if (!isac[p]) {
                ++ac;
                pena += wa[p];
                isac[p] = true;
            }
        }
        else wa[p]++;
    }
    cout << ac << " " << pena << endl;
}