ABC473 B - Old Maid
ババ抜き
考え方
タイトル通り、ババ抜き。
最初から $N$ 枚持っている設定になっているが、$1$ 枚ずつ加えていくと思う方が考えやすい。
数の集合を扱える set を使って、今の手札を管理する。
set では同じカードを $2$ 枚持つことが難しいが、今回なら何も影響がない。
$1$ 枚ずつ手札に加えていくようにしたおかげで、同じカードを複数持つ状況がないため。
ということで、カードを1枚ずつ見て、ループで以下を行う。
.contains(i)で、今回と同じカードが既にあるかどうかを判断。- なければ、
.emplace(i)で、手札に今回のカードを追加。 - あれば、
.erase(i)で、手札から今回のカードと同じものを削除。
- なければ、
全てのカードを処理したら、手札に残っているカードに書かれた数を合計すればよい。
入力例1での動作
入力を受け取る。
n: 8
a: {2, 7, 1, 8, 2, 8, 1, 8}最初、手札を表す set は空である。
カードを前から順に見ると、次のように変化する。
| 見るカード | そのカードが手札にあるか | 処理 | 処理後の手札 |
|---|---|---|---|
| $2$ | ない | $2$ を追加 | {2} |
| $7$ | ない | $7$ を追加 | {2,7} |
| $1$ | ない | $1$ を追加 | {1,2,7} |
| $8$ | ない | $8$ を追加 | {1,2,7,8} |
| $2$ | ある | $2$ を削除 | {1,7,8} |
| $8$ | ある | $8$ を削除 | {1,7} |
| $1$ | ある | $1$ を削除 | {7} |
| $8$ | ない | $8$ を追加 | {7,8} |
最後に手札へ残っているカードは $7$ と $8$ なので、答えは $7+8=15$ となる。
注意点
特になし。
別解
各数字が何枚あるかを数え、枚数が奇数である数だけを合計してもよい。