はじめに

４月も下旬に差し掛かりましたが、皆さん元気でしょうか。
どうも、きのこ派かたけのこ派なら過激たけのこ派のhayato95です。
~~キノコ派の人は、今すぐこの記事を読むのをやめましょう。~~

このシリーズについて

AtCoderの学習記録を備忘録として残しています！

前回の記事はこちら👇
1から蓄えるAtCoder備忘録 -1:全探索

使用環境は以下の通りです：

使用言語：C++
環境：Windows 11

早速：稀によく見るmapとはなんぞや

一言で言うと、キーと値をセットで管理できる配列です。

通常の配列よりも、使い勝手も管理心地も良いですね。

	通常の配列	map
添字	0, 1, 2...の整数のみ	整数でも文字列でも何でもOK
例	a[0] = 100	fruits_price["apple"] = 100

mapの使いどころ

AtCoderを解いていると、値の種類数を数えたい場面が出てきます。
例えば「複数の数値が与えられたとき、重複を除いて何種類あるか」といった場面です。

値が配列Aに、A[0]からA[n-1]のn個格納されているとして、
mapなしで解こうとすると、こうなります。

(※動作確認用のコードではなく概念説明用です)

// 二重ループで全部比較する力技
for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        if (a[i] == a[j]) {
            // 重複発見...でも管理がめんどくさい(計算量もオーバーしがち)
        }
    }
}

それが、mapを使うと簡単に求める事が出来ます！

map<int, int> cnt;  // キー：値、値：出現回数
for (int i = 0; i < n; i++) cnt[a[i]]++;  // 配列の各要素をcntに記録
cout << cnt.size() << endl;  // 種類数が一発で出る！

コードがシンプルになるだけでなく、二重ループが不要になるので処理も速くなります。

map周りの文法

キーと値って何？

mapは辞書のようなイメージです。
英和辞典で言えば、英単語がキー、日本語訳が値にあたります。

	辞書の例	コードの例
キー	英単語 "apple"	`cnt["apple"]`
値	日本語訳 "りんご"	`= 100`

宣言方法について

map<キーの型, 値の型> 変数名;

// 具体例
map<int, int> cnt;        // 整数 → 整数
map<string, int> score;   // 文字列 → 整数

<>の中には2つの型を指定します。
1つ目がキー（検索に使う値）、2つ目が値（キーに対応するデータ）の型です。

また、vectorと違ってサイズを事前に指定する必要はありません。
要素を追加するたびに自動で拡張されます。

基本操作

操作	書き方
追加・更新	`cnt[key] = value`
値を増やす	`cnt[key]++`
取得	`cnt[key]`
存在確認	`cnt.count(key)`
削除	`cnt.erase(key)`
全ループ	`for (auto [key, value] : cnt)`
種類数	`cnt.size()`

※ autoについて
autoはコンパイラ（プログラムを機械語に変換するやつ）に型を自動推論させるキーワードです。
全ループの書き方は本来こう書く必要がありますが...

for (pair<int,int> p : cnt) { ... }

autoを使うとスッキリ書けます。

for (auto [key, value] : cnt) { ... }

mapを使う上での注意

① 存在しないキーにアクセスすると勝手に作られる

map<int, int> cnt;
cout << cnt[999];  // 存在しないキーにアクセス
// → 0が返るだけでなく、cnt[999] = 0 が勝手に作られる！

存在確認には必ずcount()を使いましょう。

if (cnt.count(999)) {
    // 存在する場合の処理
}

よくある失敗例：
存在しないキーにアクセスしてしまい、意図せず空のエントリが増えてしまうケースです。
特にcnt.size()で種類数を数えたい場合、アクセスしただけで数が増えてしまいます。

cnt[1]++;
cnt[2]++;
cout << cnt.size();  // → 2のはずが...

if (cnt[999]) { }    // 存在確認のつもりがcnt[999]=0を作ってしまう
cout << cnt.size();  // → 3になってしまう！

② count()は0か1しか返さない

if (cnt.count(key))   // NG：存在するかどうかしかわからない
if (cnt[key] >= 2)    // OK：値で直接判定する

よくある失敗例：
「2回以上出てきたか」をcount()で判定しようとするケースです。
count()はキーが存在するかどうかしか返さないので、出現回数の判定には使えません。

cnt[5]++;
cnt[5]++;

if (cnt.count(5) >= 2) {  
    cout << "2回以上出てきた";　// NG：count()は1しか返さないので常にfalse
}

if (cnt[5] >= 2) {        // OK：値で直接判定
　　cout << "2回以上出てきた";
}

③ 型の混在は原則として不可

1つのmap内では型の混在はできません。
異なる型の組み合わせを使いたい場合は、別々のmapを宣言しましょう。

map<int, string> name;   // int → string用
map<int, int> score;     // int → int用

例題で試してみようのコーナー

概念が掴めたら実際の問題で確認してみましょう！

👇 mapで解けるB問題
ABC085 B - Kagami Mochi

ヒント：同じ値が２つあっても、種類としては１種類ってことは...？

まとめ

mapはキーと値をセットで管理できる配列
存在しないキーにアクセスすると勝手に作られるので注意
count()は存在確認専用（0か1しか返さない）

mapを使うタイミングの目安：
「値の種類数を数えたい」「ある値が出てきたか確認したい」場面で検討してみましょう！

最後まで付き合っていただいた方、本当にありがとうございましたm(__)m

参考文献