【第5回】はじめての競技プログラミング

set

set型は集合を表す。
set型を使うことで、要素の重複を許さず、要素の追加、削除、検索が高速に行える。
set型は重複を許さないため、既に登録した要素を再び登録しようとしても何も起こらない。(イメージは数学Aの集合)

使い方

例としてset型の変数をsとする。

関数	機能	計算量
`set<型> s;`	set型の変数`s`を宣言する	$O(1)$
`s.insert(x);`	set型の変数`s`に`x`を挿入する	$O(\log N)$
`s.erase(x);`	set型の変数`s`から`x`を削除する	$O(\log N)$
`s.count(x)`	set型の変数`s`に`x`が含まれている個数を数える	$O(\log N)$
`s.size()`	set型の変数`s`の要素数を取得する	$O(1)$
`s.empty()`	set型の変数`s`が空かどうかを調べる	$O(1)$
`s.clear()`	set型の変数`s`を空にする	$O(N)$
`*s.begin()`	set型の変数`s`の最小値を取得する	$O(1)$
`*s.rbegin()`	set型の変数`s`の最大値を取得する	$O(1)$
`set<型> s(A.begin(), A.end());`	配列`A`をset型の変数`s`に変換する	$O(N\log N)$

さらに…

C++20以降では、s.contains(x)が使える。(機能はs.count(x)と同じ)

使い方の例

int型の例

set<int> s;
for (int i = 1; i <= 5; i++) {
    s.insert(i);
}
for (int i = 1; i <= 5; i++) {
    if (s.count(i)) {
        cout << i << "は含まれています" << endl;
    } else {
        cout << i << "は含まれていません" << endl;
    }
}

set型の変数sには、1, 2, 3, 4, 5が含まれている。
1から5までの整数が含まれているかどうかを調べる。
1から5までの整数はすべて含まれているので、1は含まれています 2は含まれています 3は含まれています 4は含まれています 5は含まれていますと出力される。
string型の例

set<string> s;
s.insert("apple");
s.insert("banana");
s.insert("orange");
if (s.count("apple")) {
    cout << "appleは含まれています" << endl;
} else {
    cout << "appleは含まれていません" << endl;
}

set型の変数sには、apple, banana, orangeが含まれている。
appleが含まれているかどうかを調べる。
appleは含まれているので、appleは含まれていますと出力される。

multiset

multiset型はset型と同じく集合を表すが、要素の重複を許す。
使い方はset型と同じ。
eraseは、その要素すべてが削除される。
要素を1つだけ削除したい場合は、s.erase(s.find(x))を使う。
multiset型の場合はs.count()の計算量が $O(\log N +\text{count}(x))$ になるので注意。

multiset<int> s;
s.insert(1);
s.insert(1);
s.insert(2);
s.insert(2);
s.insert(3);
s.insert(3);
s.erase(2); // 2を削除
s.erase(s.find(3)); // 3を1つだけ削除

この場合、sには1が2つ, 3が1つ含まれている。

さらに…

C++20より、multiset型でもcontainsが使える。
要素が複数含まれる場合、containsは高速に動作する。(数えあげる動作がなく「要素があるかないか」だけを考える為)

C++のバージョンについて

C++にはいくつかバージョンがあり、バージョンによって使える機能が異なる。 C++20以降の機能を使いたい場合は、ローカルのg++のオプションを変更し、Atcoderの提出時にバージョンをC++20以上のものを選択する必要がある。

g++ -std=c++2a -o test test.cpp

または

g++ -std=c++20 -o test test.cpp

以上のコマンドでオプションとしてC++20の機能を使うことができる。 ※またAOJではC++17までしか対応していないので、C++20以降の機能を使う場合は注意が必要。

multiset<int> s;
s.insert(1);
s.insert(1);
s.insert(2);
s.insert(2);
s.insert(3);
s.insert(3);
if (s.contains(2)) {
    cout << "2は含まれています" << endl;
} else {
    cout << "2は含まれていません" << endl;
}

この場合、2は含まれていますと出力される。

問題

ヒント

forで回しながら、対象となる数値がsetに含まれているかどうかを確認しよう

解答例

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

int main() {
    set<int> st;
    int ans=0;
    for (int i = 1; i <= 5; i++) {
        int a;
        cin >> a;
        if (!st.count(a)) {
            ans++;
            st.insert(a);
        }
    }
    cout << ans << endl;
}

forで回しながら、対象となる数値がset型の変数stに含まれているかどうかを確認し、含まれていない場合はstに追加する。
stに追加する際に、追加した数値の個数をカウントする。
stに既に追加されている数字が入力された場合は、if文以降が無視されるため、カウントされない。

map

map型は「連想配列」や「辞書」と呼ばれるデータ構造を表す。
map型を使うことで、「特定の値に、ある値が紐付いている」ようなデータを簡単に扱うことができる。

使い方

例としてmap型の変数をmpとする。

関数	機能	計算量
`map<キーの型, 値の型> mp;`	map型の変数`mp`を宣言する	$O(1)$
`mp[key] = value;`	map型の変数mpに`key`と`value`のペアを挿入する	$O(\log N)$
`mp.erase(key);`	map型の変数`mp`から`key`を削除する	$O(\log N)$
`mp.at(key)`	map型の変数`mp`から`key`に対応する値を取得する	$O(\log N)$
`mp.size()`	map型の変数`mp`の要素数を取得する	$O(1)$

使い方の例

vector型のfruitsに対して、各要素の出現回数をカウントする。

map<string, int> mp;
vector<string> fruits = { "apple", "banana", "orange", "apple", "banana" };
mp["apple"] = 0;  // "apple"に対応する値を0にする
mp["banana"] = 0;  // "banana"に対応する値を0にする
mp["orange"] = 0;  // "orange"に対応する値を0にする
// fruitsの各要素に対して繰り返す
for (string fruit : fruits) {
    // fruitに対応する値を1増やす
    mp[fruit]++;
}
cout << mp["apple"] << endl;  // 2と出力される

map型の変数mpには、apple, banana, orangeがキーとして含まれている。
fruitsの各要素に対して、キーに対応する値を1増やす。
appleは2回出現しているので、2と出力される。

問題

解答例

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
int main() {
    int n;
    cin >> n;
    map<string, int> mp;
    vector<string> s(n);
    for (int i = 0; i < n; i++) {
        cin >> s[i];
        mp[s[i]]++;
    }
    int mx = 0;
    string ans;
    for (int i = 0; i < n; i++) {
        if (mp[s[i]] > mx) {
            mx = mp[s[i]];
            ans = s[i];
        }
    }
    cout << ans << endl;
}

map型の変数mpには、入力されたvector型のsの各要素がキーとして含まれている。
sの各要素に対して、キーに対応するmpの値を1増やす。
mpの各キーに対応する値が最大のものをansに代入する。

【第5回】はじめての競技プログラミング

set

使い方

さらに…

使い方の例

multiset

さらに…

問題

map

使い方

使い方の例

問題

練習問題

set型

初級

中級

上級

map型

初級

上級

【第4回】はじめての競技プログラミング

【第6回】はじめての競技プログラミング