AtCoder が提供しているABC（AtCoder Beginner Contest）289 のB問題をC++とPythonで解いてみました。ABC289は、2023年2月11日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
B問題 レ（Difficulty : 225）
問題はリンク先をご覧ください。
グラフを使って問題が定義されています。AtCoder Problems による Difficulty は 225 でした。AtCoder の問題タイトルは、英字で書かれることが多いですが、この問題は全角文字です。参考までに英語問題のタイトルは、”v” となっていました。
2023年3月6日追記 問題のリンク先が間違っていたのを修正しました。
解答案
漢文のレ点通りに読む問題です。問題で以下のように定義されています。
- 頂点に $1$ から $N$ までの番号がついた $N$ 頂点 $M$ 辺の無向グラフ $G$を考える。
- $i$ 本目の辺は頂点 $a_i$ と頂点 $a_i+1$ を結んでいる。
- 読まれていない整数が無くなるまで以下の操作を繰り返す。
- 読まれていない最小の整数を $x$ とする。頂点 $x$ が含まれる連結成分 $C$ を選び、$C$ に含まれる頂点の番号を大きい方から順に全て読む。
C++ プログラム例（ABC289B）
グラフの連結個数を求める問題は、ABC284 C問題で取り扱いました。そのプログラムをベースにします。
問題の定義通りにプログラムしました。同一連結成分に含まれる頂点は、Vector コンテナ p に格納します。連結成分の頂点を昇順にソートして、解答を表す Vector コンテナ result に格納します。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
#define N 101
vector<vector<int>> e(N);
vector<bool> seen(N, false);
vector<int> p;
void dfs(int v)
{
seen[v] = true;
p.push_back(v);
for (auto next_v : e[v]) {
if (!seen[next_v]) {
dfs(next_v);
}
}
}
int main()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int a;
cin >> a;
e[a].push_back(a + 1);
e[a + 1].push_back(a);
}
vector<int> result;
for (int i = 1; i <= n; ++i) {
if (!seen[i]) {
p.clear();
dfs(i);
sort(p.begin(), p.end(), greater<int>());
for (auto i : p) {
result.push_back(i);
}
}
}
for (int i = 0; i < n; ++i) {
cout << result[i] << " \n"[i == n - 1];
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC289B）
C++ 版と同じくABC284 C問題のプログラムをベースにします。
"""AtCoder Beginner Contest 289 B"""
def dfs(v):
seen[v] = True
p.append(v)
for next_v in e[v]:
if not seen[next_v]:
dfs(next_v)
n, m = map(int, input().split())
a = list(map(int, input().split()))
e = [[] for i in range(n + 1)]
seen = [False] * (n + 1)
for i in range(m):
e[a[i]].append(a[i] + 1)
e[a[i] + 1].append(a[i])
p = []
result = []
for i in range(1, n + 1):
if not seen[i]:
p.clear()
dfs(i)
p.sort(reverse=True)
for j in p:
result.append(j)
print(*result)こちらも「AC」と判定されました。
最後に
最初、繰り返し文を組み合わせてプログラムしましたが、正しく動作しませんでした。いろいろ試してうまくいかず、最終的に問題文の定義した通りにプログラムしたところ正しく動作しました。
引き続き ABC の問題を紹介していきます。
