まず初期状態のdeviationを計算しておく。 1回のcyclic shiftでdeviationの値がどのように変化するかを知りたい。 基本的には p[i] < iのときp[i]の位置はiに近づくので、そのような値はdeviationを1だけ減らす。 p[i]>=iのときp[i]の位置はiから離れるので…

まず与えられた木の全点対の距離を計算しておく。 これを d[u][v]: (u, v)間の距離 としておく。 d[u][v] ∈ Sかつu!=v であるような辺(u, v)をすべて持つようなグラフをHとする。このグラフでスタート地点の頂点0から探索して到達可能な頂点の集合をVとする…

ab<=bc<=caを仮定すると下の図のように解を構成できる。 実際はab, bc, caの大小関係はこのとおりとは限らない。なので、ソートしてから3個の文字列を作ってみる。あとはこの3個の文字列がa, b, cのどれに対応するかを全部試して、実際にLCSを計算してみれば…

magical bridgeの数はたかだか100個しかないので、使うmagical bridgeの数も100個以下である。di[v][a]: magical bridgeをa回使ったときのSiからvの最短距離。ただし、magical bridgeの距離は0とする。ダイクストラ法によりd1とd2を事前に計算しておく。xをm…