この問題の解説の証明部分がよくわからなかったので、自分で証明を考えました。
まず、座標正の向きに移動する行為をFと、負の向きに移動する行為をBと定義します。
そして、操作の列をFFBFBF...のように表記することにします。
ここで、高橋君の動作を、ある操作の列Sに対して、次々と次の操作を付け足す操作に対応させて考えます。
まず、連続する3つの操作を列挙してみます。
この8つの中で、図のように操作を図示すると、FBF > BFF、BFB > FBBの不等式が得られます。この不等式は、どのように地点間の距離を定めても、左項で高橋君が動く距離が右項のそれより真に長くなります。(これ以外は直接比較出来ません。)
ここで、操作BFF,FBBは禁止してしまってよい、ということが分かります。
勘の良い方ならここで気付くかもしれませんが、これは「一度向きを変えたら、その後は向きを変え続けることが最適」であることを示します。
操作列を構築しながら考えてみると、FFF...FFFBという操作列があった時に、次にBを付けると、末尾がFBBとなり禁止列となってしまうので、FBFと続けるしかありません。その次は、今度はFBFの次にFを続けるとBFFとなり禁止列となってしまうのでBFBと続けるしかありません。このように考察すると、FFF...FFFBFB...FBF(B)というような操作列が最適であることがわかります。BBB...BBBスタートの場合も同様です。
ここまで来れば、あとはこの文字列2*N通り(同一方向に進む→交互に進行方向を変えるの切り替え地点を指定する)に対して、この値を計算すればこの問題が解けます。
その部分を詳しく詰めると長くなるので省略しますが、簡単に説明すると、この操作の中で円環を(始点含む)N+1分割した中の1区間だけを通らないことになるので、その区間を基準としてFFF...FFFの長さを1づつ短くすると移動距離がどの区間分だけ(+と-のどちらに)変動するか...ということを考えると求解出来ます。
