AtCoder

ABC272 B問題(Everyone is Friends)を解く

AtCoder_ABC272_B

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 でした。ABC B問題としても、標準的な難易度です。

解答案

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

  • 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 の習熟度が上がり、楽に書けることがくることを楽しみにしています。

ABC272 について、引き続き、C問題まで紹介します。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA