AtCoder

ABC393 C問題(Make it Simple)を解く

AtCoder_ABC393_C

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 の問題を紹介していきます。

COMMENT

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

CAPTCHA