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