まず、の場所が最大値=Nなのは明らか。
また順列の並び替えなので最大値は常に1つで2つ以上存在しないので、の個数が1でないときは不適(条件1)。
PをローテートしたときはCもローテートされるので、を先頭にしておく。
いまでが確定している(以後決定した配列の左端を「左端」、配列の右端を「右端」、最大値=Nの(任意の並び方ができる)右側を「右側」と呼ぶ。)。
このときはどのような並び方でもをみたす。
次にを考える。 にたいしてが増加していたとき、左端にはより小さい値が入る(1手ローテートした結果「右側」から1つ値を削除して左端に追加する)。
このときPの右端と左端しか変更がないので、Cの値は最大でも1しか増えない。
「右側」は常に任意の並びで良いのでCの値は変化しない、左端に追加することでCの値を2増やすことはできない。
よってにたいしてが2以上増えていたら不適(条件2)
逆に条件1、2を満たしていれば、 はどのような値であっても構築できる(つまりCの値が減る分には自由)。
以下で具体的な構築方法を考えることで、これが常に満たされることを説明する。
(強いて言うなら以下まで減らすことはできないが、条件1よりそのような場合は除かれている)
Cが1増えるとき、「左端の値-1」を左端に追加することにする。
具体的には最初として、Cが増加する間は、N-1,N-2,N-3...と左端に追加していく。
のとき、右から「最大値として使われる値」に1から番号を振って、「d番目+1」を追加したい。
どういうことかは図を参照してもらって、つまりd番目より右を残して、d番目より左側は左端に追加する「d番目+1」が最大値になるようにするという感じ。
以上より「任意の値+1」が用意できれば構築できる。そして「任意の値+1」は常に「右側」に存在するようにできる。
以下はその方法。
d番目より左の値をすべて-1する。このとき大小関係は同じままなのでCの値に変化はない。
これによって欲しかった「d番目+1」は「d番目-1 +1 = d番目(だった)値」となって「d番目の値」は-1して未使用になったので「右側」に存在することになる。
(補足:-1の操作は常に可能 1回のローテートで使用されている数字の最小値は常に-1される。順列を扱っていて配列の長さも決定しているから足りなくなることはない)
以上より条件1、2を満たせば構築可能。