AtCoder が提供しているABC（AtCoder Beginner Contest）320 のD問題をC++とPythonで解いてみました。ABC320は、2023年9月16日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
D問題 Relative Position（Difficulty : 873）
問題はリンク先をご覧ください。
グラフの各頂点までの距離を求める問題として解くことができます。AtCoder Problems による Difficulty は 873 でした。
解答案
グラフの問題として解きます。
- 人がいる場所を頂点とします。
- $A_i$ から $B_i$ に辺を貼ります。辺があれば、座標の差分（diff）が設定できます。
- 座標 (0, 0) の頂点1からDFSを使って頂点を探索していきます。
- 辺で繋がっている頂点との座標の差分から、辺の先の座標（dist）を求めることができます。
- 結果的に頂点1と連結しているすべての頂点の座標が求まります。
C++ プログラム例（ABC320D）
$m$ 個の情報からグラフの辺を設定します（34、35行目）。map を使って頂点間の座標差分 diff も格納します（36、37行目）。
関数 dfs で、繋がっている頂点を探索していきます。その頂点の座標は差分から求めることができます（16、17行目）。座標を求めて、再帰的に dfs を呼び出します。
なお、頂点の座標は32ビット整数に収まらない場合があるため、64ビット整数にする必要があります。
以下が、C＋＋プログラムとなります。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
vector<vector<int>> G;
vector<bool> seen;
map<pair<int, int>, pair<ll, ll>> diff;
vector<pair<ll, ll>> dist;
void dfs(int v)
{
seen[v] = true;
for (auto next_v : G[v]) {
if (!seen[next_v]) {
dist[next_v] = make_pair(dist[v].first + diff[make_pair(v, next_v)].first,
dist[v].second + diff[make_pair(v, next_v)].second);
dfs(next_v);
}
}
}
int main()
{
int n, m;
cin >> n >> m;
G.resize(n + 1);
seen.assign(n + 1, false);
dist.resize(n + 1);
int a, b;
ll x, y;
for (int i = 0; i < m; ++i) {
cin >> a >> b >> x >> y;
G[a].push_back(b);
G[b].push_back(a);
diff[make_pair(a, b)] = make_pair(x, y);
diff[make_pair(b, a)] = make_pair(-x, -y);
}
dist[1] = make_pair(0, 0);
dfs(1);
for (int i = 1; i <= n; ++i) {
if (seen[i]) {
cout << dist[i].first << " " << dist[i].second << endl;
} else {
cout << "undecidable" << endl;
}
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC320D）
Python 版も基本的な考え方は同じです。
再帰関数の呼出回数を増やしました（4、５行目）。座標をタプルで表現したため、全体的にすっきりと書けています。
"""AtCoder Beginner Contest 320 D"""
import sys
LIMIT = 10**6
sys.setrecursionlimit(LIMIT)
def dfs(v):
seen[v] = True
for next_v in G[v]:
if not seen[next_v]:
dist[next_v] = (dist[v][0] + diff[(v, next_v)][0],
dist[v][1] + diff[(v, next_v)][1])
dfs(next_v)
n, m = map(int, input().split())
G = [[] for i in range(n + 1)]
seen = [False] * (n + 1)
diff = {}
dist = [(0, 0)] * (n + 1)
for i in range(m):
a, b, x, y = map(int, input().split())
G[a].append(b)
G[b].append(a)
diff[(a, b)] = (x, y)
diff[(b, a)] = (-x, -y)
dist[1] = (0, 0)
dfs(1)
for i in range(1, n + 1):
if seen[i]:
print(dist[i][0], dist[i][1])
else:
print("undecidable")こちらも「AC」と判定されました。
最後に
この問題は、座標平面にある点の座標を求める問題と読めます。グラフの問題として解くことが分かれば、頂点1から各頂点までの距離（座標）を求める定番の手法が使えました。
引き続き ABC の問題を紹介していきます。
