C＋＋のsetとmultisetの使い道についてのメモ

2021.06.12
IT

↓この記事で、C＋＋のSTLのコンテナについて色々列挙しましたが、使い所がわかっておりませんでした。

C++のSTLのコンテナ一覧とイテレータの説明

しかし、プログラミングコンテストの初歩問題を解いている中で使い道を見つけたので、メモします。

1. multisetについて
- 1.1. 問題文
  - 1.1.1. コード例
2. setについて
- 2.1. 問題文
  - 2.1.1. コード例

multisetについて

使えると思ったのが、この問題です。

問題文

Alice と Bob は, これらのカードを使ってゲームを行います. ゲームでは, Alice と Bob が交互に 1 枚ずつカードを取っていきます. Alice が先にカードを取ります.2 人がすべてのカードを取ったときゲームは終了し, 取ったカードの数の合計がその人の得点になります. 2 人とも自分の得点を最大化するように最適な戦略を取った時, Alice は Bob より何点多く取るか求めてください.

要は、ランダムなカードをソートをして、デカい順で、AliceとBobに割り振っていく、ということです。

ここで、INPUT時にmultiSetを使うと、自動でソートされるので(setと違い重複を許してくれる)、後はAliceとBobに簡単に割り振ることができます。

コード例

#include <iostream>
#include <set>
using namespace std;
 
//[memo]:https://atcoder.jp/contests/abs/tasks/abc088_b
int main()
{
    int n =0;
    cin >> n;
    multiset<int> card_set;
 
    for (int i = 0; i < n; i++)
    {
        int a;
        cin >> a;
        card_set.insert(a);
    }
 
    int alice = 0;
    int bob = 0;
    int counter = 0;
    multiset<int>::reverse_iterator it = card_set.rbegin();
    while (it!=card_set.rend())
    {
        if (counter%2==0)
            alice += *it;
        else
            bob += *it;
   
        *it++;
        counter++;
 
    }
    cout << alice - bob;
    return 0;
}

#include <iostream>

#include <set>

using namespace std;

//[memo]:https://atcoder.jp/contests/abs/tasks/abc088_b

int main()

{

int n =0;

cin >> n;

multiset<int> card_set;

for (int i = 0; i < n; i++)

{

int a;

cin >> a;

card_set.insert(a);

}

int alice = 0;

int bob = 0;

int counter = 0;

multiset<int>::reverse_iterator it = card_set.rbegin();

while (it!=card_set.rend())

{

if (counter%2==0)

alice += *it;

else

bob += *it;

*it++;

counter++;

}

cout << alice - bob;

return 0;

}

もっとも、ソートの昇順降順は指定できないので、取り出すときには、それを意識する必要があります。

setについて

使えると思ったのが、上記の次の問題です。

問題文

X段重ねの鏡餅 $(X \geq 1)$ センチメートルの餅をこの順に下から積み重ねると3段重ねの鏡餅になり、餅を一枚だけ置くと 1段重ねの鏡餅になります。ダックスフンドのルンルンはN $N$ $di$ センチメートルです,これらの餅のうち一部または全部を使って鏡餅を作るとき、最大で何段重ねの鏡餅を作ることができるでしょうか。

要は、重複を許さずに、並び替えて（別に並び替えなくてもOK)、その数を数えれば解けると言うものです。

コード例

#include <iostream>
#include <set>
using namespace std;
 
//[memo]:https://atcoder.jp/contests/abs/tasks/abc085_b
int main()
{
    int n =0;
    cin >> n;
    //[memo]:勝手にソート＋重複許さないセットで。
    set<int> mochi_set;
 
    for (int i = 0; i < n; i++)
    {
        int a;
        cin >> a;
        mochi_set.insert(a);
    }
　　// 処理部
    cout << mochi_set.size();
    return 0;
}