AtCoder が提供しているABC（AtCoder Beginner Contest）373 D問題をC++とPythonで解いてみました。ABC373は、2024年9月28日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Hidden Weights（Difficulty : 765）
問題の詳細は、リンク先をご覧ください。
連結しているグラフの頂点の値は一意に定まります。AtCoder Problems による Difficulty は 765 でした。
解答案
有向グラフの問題ですが、反対向きの辺の重みを $-w_j$ とすれば、逆向きの辺も定義できます。
連結しているグラフは、辺の重さを利用して頂点の値を求めることができます。「条件を満たす書き込み方が少なくとも1つ存在する」という制約から矛盾するような辺がないことが分かります。
C++ プログラム例（ABC373D）
上記の考察に基づき、頂点に値を設定していきます。
- 定番コードでグラフを定義します（6ー11および17ー24行目）。
- 連結成分を求めるために DFS を使います。
- 訪れていない頂点に対して、重み 0 で関数 dfs を呼びます（38行目）。
- 再帰関数 dfs は、ラムダ式で定義しました。
- 訪れた頂点 v の値を設定します（28行目）。
- 訪れていない頂点に対して、再帰的に関数 dfs を呼びます（31行目）。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define INF (1LL << 60)
struct Edge {
int to;
ll weight;
Edge() {}
Edge(int t, ll w) : to(t), weight(w) {}
};
int main()
{
int n, m;
cin >> n >> m;
vector<vector<Edge>> G(n + 1);
for (int i = 0; i < m; ++i) {
int u, v;
ll w;
cin >> u >> v >> w;
G[u].push_back(Edge(v, w));
G[v].push_back(Edge(u, -w));
}
vector<ll> dist(n + 1, INF);
auto dfs = [&](auto self, int v, ll w) -> void {
dist[v] = w;
for (auto next_v : G[v]) {
if (dist[next_v.to] == INF) {
self(self, next_v.to, next_v.weight + dist[v]);
}
}
};
for (int i = 1; i <= n; ++i) {
if (dist[i] == INF) {
dfs(dfs, i, 0);
}
}
for (int i = 1; i <= n; ++i) {
cout << dist[i] << " \n"[i == n];
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC373D）
Python版も基本的な考え方は同じです。再帰関数の呼び出し回数の制限（1000回）を増やしています（2、4行目）。以下がプログラムです。
"""AtCoder Beginner Contest 373 D"""
import sys
sys.setrecursionlimit(10**6)
def dfs(v, w):
global G, dist
dist[v] = w
for next_v in G[v]:
if dist[next_v[0]] == INF:
dfs(next_v[0], next_v[1] + dist[v])
INF = 1 << 60
n, m = map(int, input().split())
G = [[] for _ in range(n + 1)]
for i in range(m):
u, v, w = map(int, input().split())
G[u].append((v, w))
G[v].append((u, -w))
dist = [INF] * (n + 1)
for i in range(1, n + 1):
if dist[i] == INF:
dfs(i, 0)
print(*dist[1:])こちらも「AC」と判定されました。
最後に
今回のコンテストは、E問題（Diff 1592）以降の難易度が高く、わたしにとってはD問題までを速く解くコンテストでした。
引き続き ABC の問題を紹介していきます。
