AtCoderログ：0099 - ABC 216 B

問題

問題文

$N$ 人の人がいます。$i~(1 \le i \le N)$ 人目の人の姓は $S_i$、名は $T_i$ です。
同姓同名であるような人の組が存在するか、すなわち $1 \le i<j \le N$ かつ $S_i=S_j$ かつ $T_i=T_j$ を満たすような整数対 $(i,j)$ が存在するか判定してください。

制約

・$2 \le N \le 1000$
・$N$ は整数
・$S_i,T_i$ は英小文字のみからなる長さ $1$ 以上 $10$ 以下の文字列

回答

回答1 (AC)

2種類の vector 型変数 s, t に姓と名のデータを保持し、変数 i と j を i < j の範囲で変化させて、姓と名が一致する対があるかを調べていけば良いでしょう。$N \le 1000=10^3$ なので、繰返し回数は高々 $10^3*10^3=10^6$ なので処理可能です。コードは以下のようになりました。

abc216b-1.cpp

#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.at(i) >> t.at(i);
  }

  string answer = "No";
  for ( int i=0; i<n; i++ ) {
    for ( int j=i+1; j<n; j++ ) {
      if ( s.at(i)==s.at(j) && t.at(i)==t.at(j) ) {
        answer = "Yes"; 
        break;
      }
    }
  }

  cout << answer << endl;
}

調べたこと

AtCoder の解説 → 公式解説

回答1と同じ方針ですが、姓と名のデータを読み込む度にそれまでに読み込んだデータと一致するかを調べており、高速化がなされていました。

AtCoder の解説 → ユーザ解説

姓と名をまとめて集合型の変数に保存していき、要素数が n より小さいかどうかで重複のありなしを判定していました。なるほど。

リンク

前後の記事

• 前の記事 → AtCoderログ：0098 - ABC 216 A
• 前の記事 → AtCoderログ：0100 - 記事が100個目になりました