Polaris.AI プログラミングコンテスト 2025（AtCoder Beginner Contest 429）

　Eまで。Fは解けなくてはいけない問題だった。

コンテストへのリンク

コンテスト後のツイート

E SAFEの全点からBFSして最短と二番目に短い距離を求める。その際、同じ点から辿り着いていないように、元の頂点を覚えておくのが大事（2WA）
F 「i行目からj行目に移動するのに必要な縦移動の回数」という9要素をセグ木に乗せれば良いはず→WA

— titia (@titia_til) October 25, 2025

F - Shortest Path Query

　方針はあっていたが、セグ木の単位元を間違っていた。

　壁マスがない状態を単位元にしていたが、それはおかしい。

　「i行目→i行目の行き方のみ0手で進行可能」というのが正しい単位元だった。

　セグ木の単位元は引っ掛かりやすいポイントで、コンテスト中も注意していたけれど、一度これで良いはずと思うと修正が難しい。