本記事では先日開催された AtCoder Grand Contest 019 の C 問題の解説を試みます.
ちなみに私は本番中には解けず, 解説や他の人のコードを参考にさせていただきました.
問題はこちら
agc019.contest.atcoder.jp
スタート地点からゴール地点までの最短ルートの長さを求める問題ですね. 例からはなんとなく,
1. 最短ルートはスタート地点とゴール地点を向かい合う角とする長方形の内側(と周辺)を通る
2. ゴールが北東にある場合は, 南, 西方向に進むことはない
3. なるべく噴水に沿って90度回転する
ということが読み取れそうです. また,
4. 直線ルートよりも遠くなってしまうにも関わらず噴水に沿って180度回転する場合もある
ということも言えそうです.
これらの検証はやらないことにして, コアになるコードを作っていきます.
詳しくロジックを理解したい方は,
https://atcoder.jp/img/agc019/editorial.pdf
を参考にしてください.
