AtCoder ABC 247 B - Unique Nicknames (5Q, 灰色, 200 点)

意外と頭がこんがらがる

• 問題へのリンク

問題概要

人の人 がいて、人 の名字は 、名前は である。

各人にニックネームをつけたい。人 のニックネーム は

• または である
• かつ である任意の に対して、 かつ である

という条件を満たす必要がある。このようなニックネームの割り当てが可能かどうかを判定せよ。

制約

• 

考えたこと

条件をよく見ると、ある人のニックネームをどうするかによって、他の人のニックネームの付け方に影響を与えることがない。よって、各人 について と のいずれかが条件を満たすかどうかを調べれば良い。

人 のニックネームを にできるかを調べる方法

これは、次のように判定できる。

かつ である任意の に対して、 かつ であるかどうかを調べる。

人 のニックネームを にできるかを調べる方法

これは、次のように判定できる。

かつ である任意の に対して、 かつ であるかどうかを調べる。

まとめ

以上から、各人 に対して、そのニックネームを にする場合と、 にする場合のいずれかにできるかどうかを調べよう。

全員について「できる」ならば答えは "Yes"、そうでなければ答えは "No" となる。

この解法の計算量は となる。

コード

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

int main() {
    int N;
    cin >> N;
    vector<string> S(N), T(N);
    for (int i = 0; i < N; i++) cin >> S[i] >> T[i];

    bool res = true;
    for (int i = 0; i < N; i++) {
        // check S[i]
        bool okS = true;
        for (int j = 0; j < N; j++) {
            if (j == i) continue;
            if (S[j] == S[i] || T[j] == S[i]) okS = false;
        }

        // check T[i]
        bool okT = true;
        for (int j = 0; j < N; j++) {
            if (j == i) continue;
            if (S[j] == T[i] || T[j] == T[i]) okT = false;
        }

        if (!okS && !okT) res = false;
    }
    cout << (res ? "Yes" : "No") << endl;
}