【AtCoder】ABC 481 C - Bank Accounts

C - Bank Accounts

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

AtCoder

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 187 / NoviSteps: 5Q / 配点: 300 点

問題概要

ある銀行口座では、開設時に名前と ID を $1$ 個ずつ割り当てる。 ID の値を選ぶときは、まだ ID として使われていない正の整数のうち最小のものを採用する。

はじめ、この銀行口座はひとつも開設されていない。

以下の出来事が $Q$ 回起きるので、順に処理せよ。

• カボチャがやってきて、名前 $s$ を名乗る。
  • 名前 $s$ が割り当てられた口座が存在する場合、その ID を出力する。
  • 名前 $s$ が割り当てられた口座が存在しない場合、名前 $s$ の口座を新規に $1$ 個開設し、その ID を出力する。

制約

• $Q$ は $1$ 以上 $2 \times 10^5$ 以下の整数
• 各出来事において、$s$ は英小文字からなる長さ $1$ 以上 $10$ 以下の文字列

考察

名前をkey、 ID をvalueとする連想配列を用意して、クエリで与えられた名前が既に登録されているかどうかを確認する。

もし既に登録されていれば、対応する ID を出力する。

逆に登録されていない場合は、次に割り当てるべき ID を保持しておき、その ID を出力した後に、連想配列に名前と ID の組を登録すればよい。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.// ======================================== //
5. 
6.int main()
7.{
8.    int Q;
9.    cin >> Q;
10. 
11.    map<string, int> mp;
12.    int next_id = 1;
13.    while (Q--)
14.    {
15.        string s;
16.        cin >> s;
17. 
18.        if (mp.contains(s))
19.        {
20.            cout << mp[s] << endl;
21.        }
22.        else
23.        {
24.            cout << next_id << endl;
25.            mp[s] = next_id;
26.            next_id++;
27.        }
28.    }
29. 
30.    return 0;
31.}

https://atcoder.jp/contests/abc481/submissions/80311399

atcoder.jp

実装時間: 5 分以内

コメント

コワスギ銀行とカボチャ用銀行口座ってなんだよ。