mapを使って書きたい(ABCコンテスト091B問題)

Question

ABCコンテストの解説PDF、解説動画ではやっていなく、解説動画で解説している方がチラッとmapを使った方法を部分的にホワイトボードに書いたのでそれを参考にコードを書いたのですが手元でやった時にコンパイルはうまくいってしまうのですが欲しい答えが返ってこないので質問させていただきます。

#問題文
高橋君は青いカードを
N枚，赤いカードをM枚持っています。カードにはそれぞれ文字列が書かれており， i枚目の青いカードに書かれている文字列は si, i枚目の赤いカードに書かれている文字列は tiです。高橋君は，文字列を 1つ言います。 そして，全てのカードを確認し， その文字列が書かれた青いカードを1枚見つけるごとに 1円貰えます。 また，その文字列が書かれた赤いカードを 1枚見つけるごとに1円失います。

なお，高橋君の言った文字列と，カードに書かれた文字列が完全に一致していた場合のみを考えます。 例えば，高橋君が atcoder と言った場合，atcoderr，atcode，btcoder などと書かれた青いカードがあってもお金は貰えません(逆に，このような文字列が書かれた赤いカードがあってもお金を失うことはありません)。
高橋君は，最大で差し引き何円貰うことができるでしょうか？

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

#制約
・N,Mは整数
・1≤N,M≤100
・s1,s2,...,sN,t1,t2,...,tMは全て長さ1以上10以下の文字列で，英小文字のみからなる

とありまして、自分は以下のように書きました。

#include <iostream>
#include <map>
#include <string>
#include <vector>
using std::cin;
using std::cout;
using std::endl;

int main(){
  int n,m;
  cin >> n >> m;
  map<string,int> mp;
  vector<string> s(n);
  for (int i=0;i<n;++i) cin >> s[i];
  vector<string> t(m);
  for (int i=0;i<m;++i) cin >> t[i];
  
  for (int i=0;i<n;++i){
      mp[s[i]]++;
  }
  for (int i=0;i<m;++i){
      mp[t[i]]--;
  }
  cout << mp.size() << endl;
}

どこをどう直せばよいか教えてください。よろしくお願い致します。

Answer 1

mp.size()は要素の数(Keyの種類数？)を返すので、確かにこれだとWAになってしまいます。
問題を見たところ、高橋くんが発言するのは一回なので、
max(操作が終わったあとのmpの最大値,0)
を出力すればいいかと。
map型にmax関数があるかはわかりませんが、制約がそれほどきつくないので全探索でも間に合うはずです。

Comments

[cunwe]

返信遅れて申し訳ありません。c++のリファレンスを見るとmapには要素数を取得するmax関数は無いようでしたので全探索してみます、ご回答いただきありがとうございました！

Answer 2

cout << mp.size() << endl;

カードに書かれている文字列のバリエーション数を出力しています。
求めたいのはmpに格納されている値の最大値(ただし0以上)なのでは？

#include <algorithm>を追加して

cout << std::max(0, std::max_element(mp.begin(), mp.end())->second) << endl;

Comments

[fana]

最大値が負の場合には，答えは0にすべきように思います．
（高橋がどのカードとも一致しない文字列を言い放った場合は0なので）

[SHOMI]

https://atcoder.jp/contests/abc091/tasks/abc091_b
問題文では青いカードを入力し終えてからMを入力されるのでそこもまずいですね。

[SHOMI]

>答えは0にすべきように思います．
そうですね。コード修正しました。

[fana]

mpから最大値を探す直前で
mp[ 入力として有り得ない文字列 ] = 0;
とかなんとかして0な要素を追加しちゃうとい手段も考えられますね．特に面白いことは何もないですが．

[SHOMI]

あ、それもありですね。