問題
問題文
高橋君は青いカードを $N$ 枚，赤いカードを $M$ 枚持っています。 カードにはそれぞれ文字列が書かれており，$i$ 枚目の青いカードに書かれている文字列は $s_i$，$i$ 枚目の赤いカードに書かれている文字列は $t_i$ です。
高橋君は，文字列を $1$ つ言います。 そして，全てのカードを確認し， その文字列が書かれた青いカードを $1$ 枚見つけるごとに $1$ 円貰えます。 また，その文字列が書かれた赤いカードを $1$ 枚見つけるごとに $1$ 円失います。
なお，高橋君の言った文字列と，カードに書かれた文字列が完全に一致していた場合のみを考えます。 例えば，高橋君が atcoder と言った場合，atcoderr，atcode，btcoder などと書かれた青いカードがあってもお金は貰えません(逆に，このような文字列が書かれた赤いカードがあってもお金を失うことはありません)。
高橋君は，最大で差し引き何円貰うことができるでしょうか？
ただし，違うカードに同じ文字列が書かれていることもあることに注意してください。
制約
・$N,M$ は整数
・$1 \le N,M \le 100$
・$s_1,s_2,\ldots,s_N,t_1,t_2,\dots,t_M$ は全て長さ $1$ 以上 $10$ 以下の文字列で，英小文字のみからなる
収録されている問題セット
回答
回答1 (AC)
異なるカードに同じ文字が書かれている可能性があることから、map 型の変数を使って同じ文字の情報をまとめる必要があります。ある文字列が青いカードに書かれていれば +1 円、赤いカードに書かれていれば -1 円 となるので、map 型の変数で各文字列ごとにもらえる金額を集計するのが良いでしょう。
赤いカードと青いカードの情報を読み込んだ後、map 型の変数 money に対し、key をカードに書かれた文字列、value をもらえる/支払う金額として集約していきます。そして map の各 value に紐付いた key から最大金額を求め、それを出力することになります。
気をつけないといけないのは出力値です。単に mmax としてしまうと、最大がマイナスの場合に、お金を支払うことになってしまいます。しかしカードに書かれていない文字列を言えばもらえるお金は 0 円となり、支払わない方法は常に存在しますので、マイナスのお金をもらう、つまりお金を支払うのは避けられます。従って、出力する金額は max( mmax, 0 ) になります。
ここまでの処理をまとめると以下のコードになりました。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
string card;
map<string,int> money;
for ( int i=0; i<n; i++ ) {
cin >> card;
money[card] += 1;
}
int m;
cin >> m;
for ( int i=0; i<m; i++ ){
cin >> card;
money[card] -= 1;
}
int mmax = -1000;
for ( auto i=money.begin(); i!=money.end(); i++ ) {
if ( (i->second)>mmax ) {
mmax = (i->second);
}
}
cout << max( mmax, 0 ) << endl;
}
上のコードは $N+M$ 回の繰り返しを2回しするので、計算量は $O(2(M+N))$ となります。$N,M$ はともに小さい値なので、十分高速に処理可能です。
調べたこと
AtCoder の解説 → ユーザ解説
もらえる金額が最大になる文字列は赤いカードに書かれている必要がある(青いカードにしか書かれていないともらえる金額はマイナスになる)ので、青いカードに書かれた文字列だけで考えれば良いとのことでした。こうするとわざわざ map を持ち出す必要が無いので、コードもシンプルになりますね。また、このとき計算で算出される最大金額の最小値は 0 なので、回答1のようにマイナスを考慮する必要もないようです。
AtCoder の解説 → 公式解説
ユーザ解説と同じでした。
リンク
前後の記事
- 前の記事 → AtCoderログ：0070 - ABC 213 C