AtCoderのTwo Colors Card GameをC++で解いてみた

AtCoder

こんにちは! mnbd(@mnbbbbbd)です。

AtCoder Beginner Contest 091のTwo Colors Card Gameを解いてみましたので、その回答と解説をご紹介いたします。

プログラミング初心者なので、もっといい回答があるに違いありません。

あくまでも「動作はする」サンプルとしてご覧ください。

AtCoder Beginner Contest 091 B -Two Colors Card Game

問題文

高橋君は青いカードを N 枚,赤いカードを M 枚持っています。

カードにはそれぞれ文字列が書かれており, i 枚目の青いカードに書かれている文字列は si, i 枚目の赤いカードに書かれている文字列は ti です。

高橋君は,文字列を 1 つ言います。

そして,全てのカードを確認し, その文字列が書かれた青いカードを 1 枚見つけるごとに 1 円貰えます。

また,その文字列が書かれた赤いカードを 1 枚見つけるごとに 1 円失います。

なお,高橋君の言った文字列と,カードに書かれた文字列が完全に一致していた場合のみを考えます。

例えば,高橋君が atcoder と言った場合,atcoderr,atcode,btcoder などと書かれた青いカードがあってもお金は貰えません(逆に,このような文字列が書かれた赤いカードがあってもお金を失うことはありません)。

高橋君は,最大で差し引き何円貰うことができるでしょうか?

ただし,違うカードに同じ文字列が書かれていることもあることに注意してください。

回答

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

int main() {
       int N;
       cin >> N;
       map<string, int> blue;
       for (int i = 0; i < N; i++) {
           string s;
           cin >> s;
           blue[s]++;
       }

       int M;
       cin >> M;
       map<string, int> red;
       for (int i = 0; i < M; i++) {
           string s;
           cin >> s;
           red[s]++;
       }
 
       int money = 0;
       for (auto itr = blue.begin(); itr != blue.end(); itr++) {
            money = max(money, itr->second - red[itr->first]);
       }
       cout << money << endl;
       return 0;
}

解説

青カード、赤カードそれぞれ連想配列を使用します。

キーに文字列、値にその文字列のカウント数になります。

それぞれのカード数をループで回して、受け取った文字列を連想配列のキーに当てはめてカウントします。

赤のカードでも同じようにループします。

後は青のカードのカウント数からそのキーの同じ赤のカードのカウント数の差を出して、最大値と比較して、大きければ代入し直しています。

私がハマったポイント

カードのデータ構造を配列にしようとしてしまったため、文字列とカウント数の連結をどうやっていいかわからなくなりました。

学んだこと

C++の連想配列を知りました。

pythonとはまた違う感じです。

まとめ

AtCoder Beginner Contest 091のTwo Colors Card GameをC++で解いてみた回答と解説でした。

以上です。
読んでいただきありがとうございました!