AtCoder が提供しているABC（AtCoder Beginner Contest）313 のB問題をC++とPythonで解いてみました。ABC313は、2023年8月5日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
B問題 Who is Saikyo?（Difficulty : 213）
問題はリンク先をご覧ください。
グラフの問題と考えてDFSで解きました。スマートな解法も紹介します。AtCoder Problems による Difficulty は 213 でした。
解答案
コンテスト本番では、グラフの問題としてDFSを使って解きました。
具体的には、強さの関係を有向グラフと捉えて、ある頂点から残りすべての頂点に遷移できるような頂点があるか調べました。
公式解説では、もっとスマートな解法が紹介されていましたので、合わせて紹介します。
C++ プログラム例（ABC313B）
変数の宣言（4、5行目）、関数 dfs の実装（7ー15行目）は、グラフ処理の定番コードを使っています。読み込んだ a と b を向きが有る辺と考えてグラフを構築します（26行目）。
すべての頂点について、以下を確認します。
- 頂点を通ったかのフラグ seen を初期化する（30行目）。
- 関数 dfs を呼び出して、すべての頂点をたどる（31行目、および関数 dfs）。
- 自分も含めた頂点をすべてを通っているか調べて、通っていたらその頂点が解になる（32ー41行目）。
すべての頂点で上記を満たさない場合は、-1 を出力します。B問題としてはコードが長くなっていますが、多くは定番コードとなっています。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> G;
vector<bool> seen;
void dfs(int v)
{
seen[v] = true;
for (auto next_v : G[v]) {
if (!seen[next_v]) {
dfs(next_v);
}
}
}
int main()
{
int n, m;
cin >> n >> m;
G.resize(n + 1);
seen.assign(n + 1, false);
for (int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b;
G[a].push_back(b);
}
for (int i = 1; i <= n; ++i) {
seen.assign(n + 1, false);
dfs(i);
bool result = true;
for (int j = 1; j <= n; ++j) {
if (!seen[j]) {
result = false;
}
}
if (result) {
cout << i << endl;
return 0;
}
}
cout << -1 << endl;
return 0;
}上記の DFS を使った解法は、わたしにとっては考えやすかったです。ただし、もっとスマートな考え方がありました。以下、公式解説を参考にしました。
強さの関係 Ai → Bi が与えられます。このとき、最強のプログラマは Bi に表れません。このとき、Bi として与えられない頂点（人）がひとつの場合、これが解になります。この頂点が孤立していないことは、「全ての相異なる2人組にどちらが強いかを割り当てる方法が少なくとも1通り存在する」という制約から分かります。
Bi として与えられない頂点（人）が複数あれば、その場合は最強のプログラマはいません。入力例2や3の場合が該当します。
以下のプログラムとなります。グラフを使ったプログラムより簡潔になりました。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<int> w(n + 1, 0);
for (int i = 0; i < m; ++i) {
int a, b;
cin >> a >> b;
++w[b];
}
int result;
int kouho = 0;
for (int i = 1; i <= n; ++i) {
if (w[i] == 0) {
++kouho;
result = i;
}
}
if (kouho == 1) {
cout << result << endl;
} else {
cout << -1 << endl;
}
return 0;
}どちらも AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC313B）
C++ の後者のプログラムを移植しました。
"""AtCoder Beginner Contest 313 B"""
n, m = map(int, input().split())
w = [0] * (n + 1)
for i in range(m):
a, b = map(int, input().split())
w[b] += 1
kouho = 0
for i in range(1, n + 1):
if w[i] == 0:
kouho += 1
result = i
print(result if kouho == 1 else -1)こちらも「AC」と判定されました。
最後に
グラフの問題として解きました。コード自体は長くなりましたが、9分程度でAC判定を取れました。ただし、公式解説のような解法が最初に思いつけば、より速くACが取れたと思われます。解けた問題でも学びがありました。
引き続き ABC の問題を紹介していきます。
