木構造の距離を求める問題演習として, AtCoder Beginner Contest 070 の D 問題の解説をしてみます.
問題はこちら
abc070.contest.atcoder.jp
重み付き木構造上の2点間の距離を求めるアルゴリズムを python で書いてみる
グラフの一種である木構造での距離を求めるアルゴリズムを考えます.
グラフとは
詳しくは グラフ理論 - Wikipedia などの記述をご参照ください.
グラフ(graph)とは頂点(vertex)と辺(edge)からなる構造を表しており, 頂点同士が辺によって繋がっていることを表しているものです（頂点の集合は自然数の部分集合と同型なので, それぞれの頂点には何番目の頂点かを表す自然数が割り当てられます. 一般には辺それぞれには実数の重みがあり, その頂点同士の移動にかかるコストを表しています. 辺は の形式を持ち, 頂点
から頂点
はコスト
で隣接していることを表しています. 重み付きでない場合は,
と理解します.
辺に向きがあるもの（つまり, 2つの頂点について行けるのに戻れなかったりコストが等しくなかったりするもの）を有向グラフ(directed graph), 辺に向きがないもの（つまり, 頂点間のコストは行きと帰りで等しいもの）を無向グラフ(undirected graph)といいます. 無向グラフでは なる辺があったとき, 逆向きの
を辺にもつ有向グラフと解釈することもできます.
AGC019 の C 問題を python で解いてみる。
本記事では先日開催された AtCoder Grand Contest 019 の C 問題の解説を試みます.
ちなみに私は本番中には解けず, 解説や他の人のコードを参考にさせていただきました.
問題はこちら
agc019.contest.atcoder.jp
スタート地点からゴール地点までの最短ルートの長さを求める問題ですね. 例からはなんとなく,
1. 最短ルートはスタート地点とゴール地点を向かい合う角とする長方形の内側(と周辺)を通る
2. ゴールが北東にある場合は, 南, 西方向に進むことはない
3. なるべく噴水に沿って90度回転する
ということが読み取れそうです. また,
4. 直線ルートよりも遠くなってしまうにも関わらず噴水に沿って180度回転する場合もある
ということも言えそうです.
これらの検証はやらないことにして, コアになるコードを作っていきます.
詳しくロジックを理解したい方は,
https://atcoder.jp/img/agc019/editorial.pdf
を参考にしてください.
