AtCoder

ABC303 B問題(Discord)を解く

AtCoder_ABC303_B

AtCoder が提供しているABC(AtCoder Beginner Contest)303 のB問題をC++とPythonで解いてみました。ABC303は、2023年5月27日21:00に実施されました。

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

B問題 Discord(Difficulty : 112)

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

ABC303 B問題 Discord

set コンテナを使って、重複しないペアの個数をカウントする問題です。AtCoder Problems による Difficulty は 112 でした。

解答案

C++ プログラム例(ABC303B)

並んでいるペアを set コンテナに登録していきます。重複を避けるため、$i \leqq j$ となるようにペア $(i, j)$ を登録します(18行目の if 文)。

$n$ 人から2人選ぶ組み合わせは、$n(n-1)/2$ 通りです。これから set コンテナのサイズを引くと、「不仲である可能性がある二人組の個数」を得ることができます(26行目)。

以下が、C++プログラムとなります。set に関する行の背景色を変更しています。

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

int main()
{
	int n, m;
	cin >> n >> m;
	vector<vector<int>> a(m, vector<int>(n));
	for (int i = 0; i < m; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> a[i][j];
		}
	}

	set<pair<int, int>> p;
	for (int i = 0; i < m; ++i) {
		for (int j = 0; j < n - 1; ++j) {
			if (a[i][j] <= a[i][j + 1]) {
				p.insert(make_pair(a[i][j], a[i][j + 1]));
			} else {
				p.insert(make_pair(a[i][j + 1], a[i][j]));
			}
		}
	}

	cout << n * (n - 1) / 2 - p.size() << endl;

	return 0;
}

AC(Accepted=正しいプログラム)と判定されました。

Python プログラム例(ABC303B)

Python は、{} で初期化すると辞書になります。set を使うためには、set() で初期化する必要があります(7行目)。ロジックは、C++版と同じです。set に関する行の背景色を変更しています。

"""AtCoder Beginner Contest 303 B"""
n, m = map(int, input().split())
a = [[0 for i in range(n)] for j in range(m)]
for i in range(m):
    a[i] = list(map(int, input().split()))

p = set()
for i in range(m):
    for j in range(n - 1):
        if a[i][j] <= a[i][j + 1]:
            p.add((a[i][j], a[i][j + 1]))
        else:
            p.add((a[i][j + 1], a[i][j]))

print(n * (n - 1) // 2 - len(p))

こちらも「AC」と判定されました。

最後に

N と M が50以下なので、配列で処理してもよいですが、このような問題は set を使っています。

ABC303 について、引き続き問題を紹介していきます。

COMMENT

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

CAPTCHA