【AtCoder】ABC 343 D - Diversity of Scores | 茶コーダーが解くAtCoder

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 422

問題概要

から までの番号が付けられた 人の選手がいる。初めは全員0点である。今から 秒後に選手 の得点が 点増加する。今から 秒後の時点における、 人の選手の得点の種類をそれぞれ出力せよ。

制約

• 入力はすべて整数
• 
• 
• 

考察

出力時に問われているのは「選手たちの得点の種類」だから、各時刻で、ある得点に対して「その得点を何人が持っているのか」が分かればよい。したがって、得点をkey、その得点を持つ選手の人数をvalueとする連想配列を作成する。C++ではmap型が使えるだろう。ここではmap<long long, long long>型の変数として、mpを用いた。

また、各選手の得点を記録する配列も必要。これは得点の更新の際に必要となる。ここではvector<long long>型の変数として、scoresを用いた。処理は以下のようになる。

• 初期化時はmp[0] = Nで行う。

• 秒後に選手 の得点が 点増加するとする。まず、得点 ] の人数が一人減るのだから、mp[scores[A_i]]--;である。このとき、mp[scores[A_i]] = 0となった場合は、その要素を削除しなければならないことに注意する。残したままだと、出力時に余計に加算されてしまう。

• 次に、選手 の得点に 点を追加する。scores[A_i] += B_iで良いだろう。

• そして、連想配列の情報を更新していく。C++のmapは存在しないkeyにアクセスすると勝手にvalue = 0で初期化してくれるので、mp[scores[A_i]]++とすればよい。

• 最後に、得点の種類を出力する。これはmp.size()に対応する。

以上の説明は1-indexedで書いたが、コードでは0-indexedとしている。

コード

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

#define rep(i, start, end) for (ll i = (start); i < (ll)(end); i++)

using ll = long long;

// ======================================== //

int main()
{
    int N, T;
    cin >> N >> T;
    vector<ll> scores(N, 0);
    map<ll, ll> mp;

    mp[0] = N;
    rep(i, 0, T)
    {
        int A, B;
        cin >> A >> B;

        mp[scores[A - 1]]--;
        if (mp[scores[A - 1]] == 0)
            mp.erase(scores[A - 1]);

        scores[A - 1] += B;
        mp[scores[A - 1]]++;

        cout << mp.size() << endl;
    }
}

atcoder.jp

実装時間: 45分