以下をそれぞれ操作1、操作2 と呼ぶことにします。

1. 全体をひっくりかえす。つまり、\(p_1,p_2,\dots,p_n\) を \(p_n,p_{n-1},\dots,p_1\) に並び替える。
2. 先頭の項を末尾に移動させる。つまり、\(p_1, p_2, \dots,p_n\) を \(p_2,\dots, p_n, p_1\) に並び替える。

解法A

問題文中の操作で \(1,2,\dots,n\) にできる順列は、以下の \(2n\) 通りしかありません（\(n=2\) のときは重複があるため\(2\) 通りです）。

• 操作2で昇順に並び替えられるもの
  • \(1,2,3,\dots,n\)
  • \(2,3,\dots,n,1\)
  • \(3,\dots,n,1,2\)
  • \(\vdots\)
  • \(n,1,2,3,\dots,n-1\)
• 操作2で降順に並び替えられるもの
  • \(n,n-1,n-2,\dots,1\)
  • \(n-1,n-2,\dots,1,n\)
  • \(n-2,\dots,1,n,n-1\)
  • \(\vdots\)
  • \(1,n,n-1,n-2,\dots,2\)

よって、途中の状態としてありうるものが \(O(n)\) 個しかないため、基本的には全探索で解くことができます。 ただし、入力として与えられる長さ \(n\) の配列をそのまま使って愚直に全探索をしてしまうと、各操作に \(O(n)\) かかってしまうため、状態の持ち方を工夫する必要があります。 例えば、各状態を以下の情報の組として持てば良いです。

• \(1\) の位置
• 操作2だけで昇順に並び替えられるかどうか

C++による実装例

解法B

操作2 → 操作1 → 操作2 と操作すると、操作1 だけをしたときと同じ結果になります。 よって、操作2 → 操作1 → 操作2 という操作を考える必要がありません。

同様に、操作1 → 操作1 という操作も、何もしてないのと同じ結果になるため、考える必要がありません。

以上から、操作1 は最初か最後にしかしなくてよいことが分かります。 よって、最初に操作1をするかどうかと、最後に操作1をするかどうかを計 \(4\) 通り試し、うまくいったものの最小値を取ればよいです。