ABC393 C問題（Make it Simple）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）393 C問題をC++とPythonで解いてみました。ABC393は、2025年2月15日21:00に実施されました。

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

C問題 Make it Simple（Difficulty : 188）

問題の詳細は、リンク先をご覧ください。

ABC393 C問題 Make it Simple

自己ループと多重辺となる辺を除いてカウントします。AtCoder Problems による Difficulty は 188 でした。

解答案

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

特定の辺を除いた辺をカウントする問題です。自己ループと多重辺を除きます。頂点が同じ辺が自己ループです（12ー14行目）。set コンテナ e に辺 $(u,v)$ を $u<v$ となるように格納します。与えられた辺の数 m から、e の要素数を引いた値を出力します。

以下が、C++プログラムです。

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

int main()
{
	int n, m;
	cin >> n >> m;
	set<pair<int, int>> e;
	for (int i = 0; i < m; ++i) {
		int u, v;
		cin >> u >> v;
		if (u == v) {
			continue;
		}
		if (u > v) {
			swap(u, v);
		}
		e.insert(make_pair(u, v));
	}

	cout << m - (int)e.size() << endl;

	return 0;
}

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

Python プログラム例（ABC393C）

Python版も基本的な考え方は同じです。以下がプログラムです。

"""AtCoder Beginner Contest 393 C"""
n, m = map(int, input().split())

e = set()
for i in range(m):
    u, v = map(int, input().split())
    if u == v:
        continue
    if u > v:
        u, v = v, u
    e.add((u, v))

print(m - len(e))

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

最後に

グラフ特有のアルゴリズムは必要ではなく、条件を満たす辺の数をカウントするだけでした。

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