問題
既存投稿一覧ページへのリンク
補足
2025年2月15日時点、AtCoderの問題に対して挑むのは、まだ実力不足だと思い知ったので、スランプを脱するまで問題を解くのに必要なアルゴリズムを小分けで学習するスタンスに切り替えました。
DFS
木の直径計算(ABC 361 E)
sample.py
# 木の直径計算関数の実装
# 深さ優先探索（DFS）を行い、指定された頂点から最も遠い頂点とその距離を求める関数
def dfs(G, v, p):
# res: (最大距離, 最も遠い頂点)
res = (0, v)
# 現在の頂点vの隣接頂点uとそのコストcについてループ
for u, c in G[v]:
# 親頂点pへの逆戻りを防ぐ
if u == p:
continue
# 隣接頂点uから再帰的にDFSを行う
dist = dfs(G, u, v)
# より遠い頂点が見つかった場合、結果を更新
if dist[0] + c > res[0]:
res = (dist[0] + c, dist[1])
return res
# 木の直径を計算する関数
def tree_diameter():
# テスト用の木構造 (0-1-2-3 の直線状、各辺コスト1)
G = [
[(1, 1)], # 頂点0: 頂点1に接続（コスト1）
[(0, 1), (2, 1)],# 頂点1: 頂点0と2に接続（各コスト1）
[(1, 1), (3, 6)],# 頂点2: 頂点1と3に接続（頂点1はコスト1, 頂点3はコスト6）
[(2, 2)] # 頂点3: 頂点2に接続（コスト2）
]
# 任意の頂点（ここでは2）から最も遠い頂点を見つける
_, far = dfs(G, 2, -1)
# 見つかった最も遠い頂点からさらに最も遠い頂点までの距離（直径）を求める
diameter, other_node = dfs(G, far, -1)
return diameter, far, other_node
if __name__=="__main__":
diameter, far, other_node = tree_diameter()
print(f"距離: {diameter}")
print(f"始点: {far}, 終点: {other_node}")
1回目のDFSで1番遠いノードを調べる
開始点：頂点2→検出点：頂点2
2回目のDFSで一番遠いノードから見て、1番遠いノードを調べる
開始点：頂点0→検出点：頂点3
有向グラフにおけるDFSを用いた最遠点と最大距離の探索
sample.py
def dfs(G, v, parent):
# 現在の頂点からの最大距離を初期化
max_dist = 0
# 最遠点を現在の頂点で初期化
farthest_node = v
# 現在の頂点の隣接頂点と辺の重みをループ
for u, c in G[v]:
# 親頂点でない場合のみ処理
if u != parent:
# 隣接頂点から再帰的にDFSを実行
dist, node = dfs(G, u, v)
# より遠い頂点が見つかった場合
if dist + c > max_dist:
# 最大距離を更新
max_dist = dist + c
# 最遠点を更新
farthest_node = node
# 最大距離と最遠点を返す
return (max_dist, farthest_node)
def find_farthest_node():
G = [ # グラフの隣接リストを定義
[(1, 10), (2, 5)], # 頂点0の隣接情報
[(0, 3)], # 頂点1の隣接情報
[(0, 5), (3, 2)], # 頂点2の隣接情報
[(2, 2)] # 頂点3の隣接情報
]
return dfs(G, 1, -1) # DFSを開始点1から実行し、最遠点を返す
if __name__=="__main__":
max_dist, farthest_node = find_farthest_node()
print(f"最大距離: {max_dist}, 最遠点: {farthest_node}")
DFSで1番遠いノード(重みが大きいノード)を調べる
無向グラフの全コスト - 木の直径コスト
sample.py
def dfs(G, v, parent):
res = (0, v)
for u, c in G[v]:
if u != parent:
dist = dfs(G, u, v)
if dist[0] + c > res[0]:
res = (dist[0] + c, dist[1])
return res
def calculate_total():
# 4頂点の木構造 (0-1: 2, 1-2: 3, 1-3: 4)
edges = [
(0, 1, 2),
(1, 2, 3),
(1, 3, 4)
]
total = sum(c for _, _, c in edges)
# 木構造の構築
G = [[] for _ in range(4)]
for a, b, c in edges:
G[a].append((b, c))
G[b].append((a, c))
# 直径計算
_, far = dfs(G, 0, -1)
diameter, _ = dfs(G, far, -1)
return 2 * total - diameter
if __name__=="__main__":
print("総コスト－直径コスト:", calculate_total())
頂点0から見た最遠の頂点
頂点3から見た最遠の頂点
全頂点の総コストから木の直径のコストを除算
