ABC272 B問題（Everyone is Friends）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）272 のB問題をC++とPythonで解いてみました。ABC272は、2022年10月8日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

B問題 Everyone is Friends（Difficulty : 139）

問題はリンク先をご覧ください。

ABC272 B問題 Everyone is Friends

整数列を読みながら、処理をする必要があります。AtCoder Problems による Difficulty は、139 でした。

解答案

問題を解く方針を書きだします。

• N と M を読み込む。
• M 行読み込み以下を行う。
  • 例えば、3 1 2 3 を読みこんだ時、最初の 3 は後ろの人の数です。
  • (1, 2) のペアを登録します。次に (1, 3) 、(2, 3) のペアを登録します。
• 登録されたペアの数を確認して、解答を出力する。

n 人いれば、2人の組は、$_nC_2 = n(n – 1) / 2$ 個あります。登録されたペアの数と比較して一致していれば、”Yes” を出力します。一致していなければ（登録されたペアの方が少なければ）ペアになっていない組があるため、”No” を出力します。

C++ プログラム例（ABC272B）

C++ では、set コンテナを使います。set コンテナ p の要素は、人の組とします。2行目以降、M行を読み込み、ペアを次々と p に登録しています。set コンテナは重複する要素を無視します。

最後に、p が持つ要素の個数と $_nC_2 = n(n – 1) / 2$ を比較して、解を出しています。

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

int main()
{
	int n, m;
	cin >> n >> m;

	set<pair<int, int>> p;

	for (int i = 0; i < m; ++i) {
		int kn;
		cin >> kn;
		vector<int> x(kn);
		for (int j = 0; j < kn; ++j) {
			cin >> x[j];
		}
		for (int j = 0; j < kn; ++j) {
			for (int k = j + 1; k < kn; ++k) {
				p.insert(make_pair(x[j], x[k]));
			}
		}
	}

	if (n * (n - 1) / 2 == p.size()) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}

	return 0;
}

このプログラムは、AC（Accepted＝正しいプログラム）と判定されました。

Python プログラム例（ABC272B）

Python でも、set 型の変数にぺア（タプル）を加えていきます。その結果の重複を取り除いたペアの数を確認しています。C++ でやっていることと同じです。

"""AtCoder Beginner Contest 272 B"""
n, m = map(int, input().split())

p = set()
for i in range(m):
    x = list(map(int, input().split()[1:]))
    for j in range(len(x)):
        for k in range(j + 1, len(x)):
            p.add((x[j], x[k]))

if n * (n - 1) // 2 == len(p):
    print("Yes")
else:
    print("No")

Python 版も「AC」と判定されました。

最後に

C++ も Python も重複を許さないコンテナを使って実装しました。今は、C++ の実装をまねしながら、Python のプログラミングを書いている状況です。Python の習熟度が上がり、楽に書けることがくることを楽しみにしています。

引き続き ABC の問題を紹介していきます。