1455

N人が座っている円卓で、隣接する二人をスワップするという操作を何回やれば、両隣の人が逆転した状態にできるか答えよ、という問題。

N人をK人とN-K人に分けて、それぞれをスワップ操作で逆順にすることを考える。K人のスワップは、2K-3回のスワップとK-2人のスワップの和でできるので、先にテーブルを作っておく。あとは最適なKを求めるだけだけれど、一般的にはKとN-Kが近い方が良い。