はまやんはまやんはまやん

hamayanhamayan's blog

Two Colors Card Game [AtCoder Beginner Contest 091 B]

https://beta.atcoder.jp/contests/abc091/tasks/abc091_b

解法

https://beta.atcoder.jp/contests/abc091/submissions/2225811

問題に取り組む基本として「全探索できる所を探す」という方針がある。
今回は高橋君の言うべき文字列を全探索して問題を解くことにしよう。
 
ここからは少し考察なのだが、高橋君の言うべき文字列はなんだろうか。
青カード、赤カードにかかれていない文字列を言うと点数は0となるので、これは考える必要がない。
そのため、言うべき文字列はカードにかかれている文字列ということになる。
これは最大200個なので、全探索しても問題なさそうだ。
更に言うと、点数が正の数になるためには、青カードにかかれている文字を使う必要がある。
そのため、青カードにかかれている文字から高橋君が言う文字列を選ぶ全探索を行う。
 
si番目の青カードの文字列を言った時のポイントは愚直なシミュレーションで計算する。
ポイントの最大値が答え。
O(N*(N+M))

int N, M;
string S[101], T[101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> S[i];
    cin >> M;
    rep(i, 0, M) cin >> T[i];
 
    int ans = 0;
    rep(si, 0, N) {
        int point = 0;
        rep(i, 0, N) if (S[i] == S[si]) point++;
        rep(i, 0, M) if (T[i] == S[si]) point--;
        ans = max(ans, point);
    }
    cout << ans << endl;
}