AtCoder解説 コーナーケース

はじめに

AtCoderの過去問を解いていて、なぜかWAになってしまう。
その原因を特定するのに時間がかかってしまった問題についてまとめようと思います。
自分が解説記事調べた時にほしかった情報です。

ABC216-B

$N$人の人がいて、
$i$人目の人の苗字が$S_i$で、名前が$T_i$です。
$N$
$S_1$ $T_1$
$S_2$ $T_2$
$\vdots$
$S_N$ $T_N$

同姓同名の人がいる場合$Yes$を、いないなら$No$を出力するという問題です。

方針としては、ハッシュマップを用意し、すべての名前を登録しておきます。
例えばaokiさんが2回現れると
$mp[aoki] = 1$
$mp[aoki] = 2$
という風に右側のinteger型の値が増えていきます。
全てを登録し終えたら、ハッシュマップの値すべてを探索し、右側の値が2以上のものがあれば$Yes$を出力します。

注意点(コーナーケース)
「青木 太郎(あおき たろう)」さんと、
「青 喜多朗（あお きたろう）」さん
は別人ですが、アルファベット表記では同姓同名と判断されてしまいます。そのため、苗字と名前の区切りをはっきりさせておく必要があります。

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

int main(){
    int N; cin >> N;

    //ハッシュマップを作る
    unordered_map<string,int> mp;

    for(int i = 0; i < N; i++){
        string x,y; cin >> x >> y;
        /*
        ここで、
        string z = x + y
        としてはだめ
        */
        string z = x + " " + y;
        mp[z]++;
    }

    for(auto &[key,value]:mp){
        if(mp[key]>1){
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;
    return 0;
}

ABC247-B

$N$人の人がいて、
$i$人目の人の苗字が$S_i$で、名前が$T_i$です。
$N$
$S_1$ $T_1$
$S_2$ $T_2$
$\vdots$
$S_N$ $T_N$
問題文を言い換えると、$i$人目の人の苗字か名前どちらか一方がユニーク(ほかの人と重複しない)場合は$Yes$を出力するという問題です。

方針としては、ハッシュマップを用意し、すべての苗字と名前を一つのハッシュマップに登録しておきます。
その後、$N$人の苗字と名前それぞれについて、ユニークかどうか調べ、全員に対して成り立つかどうかを検証します。

注意点(コーナーケース)
苗字==名前のケース!!
3
tanaka tarou
suzuki jirou
kondou kondou
上記のようなケースでは、
kondouさんのあだ名はkondouでもいいはずですが
ハッシュマップ上ではmp[kondou]=2
という風に重複があるとみなされてしまいます

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

int main(){
    int N; cin >> N;
    vector<vector<string>> S(N,vector<string>(2));
    unordered_map<string,int> mp;

    for(int i = 0; i < N; i++){
        string x,y; cin >> x >> y;
        S[i][0] = x; S[i][1] = y;
        mp[x]++;
        mp[y]++;

        //以下の一文が必要
        if(x==y) mp[x]--;
    }

    for(int i = 0; i < N; i++){
        if(mp[S[i][0]] != 1 and mp[S[i][1]] != 1){
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
    return 0;
}

おわりに

他にもWAだけど一見どこが間違ってるのかわからないような問題に遭遇しましたら本記事に追加していく予定です。
間違いや質問等ありましたらご遠慮なくコメントください。