はじめに
４月も下旬に差し掛かりましたが、皆さん元気でしょうか。
どうも、きのこ派かたけのこ派なら過激たけのこ派の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