コンテストでの時間切れや解けなかった過去問を振り返って供養していく
問題
Difficulty: 1945 (記事作成時点)
供養
解法
- 元のグラフを $G = (V, E)$ とする
- パス $v_{1}, \dots, v_{N}$ が回文になるということは、$v_{1}$ および $v_{N}$ からそれぞれ同じ記号の辺を通るように辿って、同じ点もしくは隣接点に到達することを意味する
- $v_{1}$ から伸びるパスのもう一方の端点 $v_{i}$ および $v_{N}$ から伸びるパスのもう一方の端点 $v_{j}$ のペア $(v_{i}, v_{j})$ に対応する頂点からなる、頂点数 $N^{2}$ のグラフ $G^{'}$ を作る
- 辺 $(a, b)$ および $(c, d)$ が同じ記号のとき、$G^{'}$ に以下の8本の有向辺（4本の無向辺）を張る
- $\left( (a, c), (b, d) \right)$
- $\left( (a, d), (b, c) \right)$
- $\left( (b, c), (a, d) \right)$
- $\left( (b, d), (a, c) \right)$
- $\left( (c, a), (d, b) \right)$
- $\left( (c, b), (d, a) \right)$
- $\left( (d, a), (c, b) \right)$
- $\left( (d, b), (c, a) \right)$
- 作成した $G$ 上で点 $(1, N)$ からの距離 $D_{(v_{i}, v_{j})}$ を求める
- $u \in V$ について $2 \times D_{(u, u)}$、 $(u, v) \in E$ について $2 \times D_{(u, v)} + 1$ および $2 \times D_{(v, u)} + 1$ の中から最小値を出力する
実装
計算量は $O(N^{2} + M^{2})$
公式解説
躓いた点
- 頂点数 $N^{2}$ のグラフを作ることを思いつかなかった
