答えの予想、および解法

二つ目の入出力例を見てみましょう。

• 入力 : \(\, 9, 8, 6, 5, 10, 3, 1, 2, 4, 7\)
• 出力 : \(\, 9, 8, 6, 5, 10, 2, 7, 4, 3, 1\)

これを観察すると、次のようなことが分かります。

• 末尾 \(5\) 項のみが変化しており、先頭 \(5\) 項は等しい。
• 入力の末尾 \(4\) 項は単調増加であり、出力の末尾 \(4\) 項は単調減少である。

二つ目の性質 (入力の末尾 \(4\) 項は単調増加) より、末尾 \(4\) 項のみを並べ替えて与えられた順列より辞書順で小さいものを構成することはできません。よって、少なくとも末尾 \(5\) 項を並べ替える必要があり、一つ目の性質 (先頭 \(5\) 項は変化しない) は、「先頭に近い要素はなるべく変化させない」ことを表していると予想できます。この予想は次節で証明します。

これを一般化しましょう。\(P \neq (1, \dots, N)\) なので、\(P_n \gt P_{n + 1} \lt P_{n + 2} \lt \dots \lt P_N\) となるような \(n\) がとれます。\(P_{n + 1}, \dots, P_N\) のみを並べ替えて \(P\) より辞書順で小さい順列を構成することはできないので、「先頭に近い要素はなるべく変化させない」ということは、答えは \(P_n, \dots, P_N\) のみを入れ替えたものとなります。さらに、第 \(n\) 項は必ず異なる値になります (でなければ、\(P_{n + 1}, \dots, P_N\) のみを並べ替えるのと同じです) 。

先頭 \(n-1\) 項は変化させず、第 \(n\) 項は変化させるので、\(P\) より辞書順で小さくなることは、第 \(n\) 項が \(P_n\) より小さくなることと同値です。答えは、\(P\) より辞書順で小さい順列のうち最大のものなので、第 \(n\) 項を \(P_n, \dots, P_N\) のうち \(P_n\) 未満で最大のものにしなければなりません。そして、このもとで、第 \(n+1\) 以降はどのように並べても得られる順列は辞書順で \(P\) より小さくなります。よって、第 \(n+1\) 以降を辞書順で最大にする、すなわち残った要素を降順に並べれば答えが得られます。

以上の内容は \(O(N)\) で実装することができます。実装例を次に示します。

実装例 (C++)
実装例 (Python)

予想の証明

さて、前節の予想を証明しなければ解けたことにはなりません。
以下では数列 \(A, B\) に対し、\(A\) が \(B\) より辞書順で小さいことを \(A \lt B\) と表します。

順列 \(X, Y\) が \(X \lt P, Y \lt P\) を満たすならば、以下の条件を満たす \(1\) 以上 \(N\) 以下の整数 \(n, m\) が存在します。

• \((X_1, \dots, X_{n - 1}) = (P_1, \dots, P_{n - 1}), X_n \lt P_n\)
• \((Y_1, \dots, Y_{m - 1}) = (P_1, \dots, P_{m - 1}), Y_m \lt P_m\)

すると、\(n \lt m\) ならば \(X \lt Y\) であることが以下の二つから分かります。

• \((X_1, \dots, X_{n - 1}) = (P_1, \dots, P_{n - 1}) = (Y_1, \dots, Y_{n - 1})\)
• \(X_n \lt P_n = Y_n\)

よって、 \(P\) よりも辞書順で小さい順列のうち最大ものものは、先頭から見て初めて \(P\) とは異なる値が現れる位置が最も後ろであるものだということが示せました。

従って、「先頭に近い要素はなるべく変化させない」という予想は正しかったことがわかります。

別解 : 標準ライブラリの利用

C++ には std::prev_permutation という関数が存在します。 std::prev_permutation(std::begin(P), std::end(P)) とすると、\(P\) の要素を並べ替えて得られる数列のであって、\(P\) よりも辞書順で小さいもののうち最大のものが \(P\) に格納されます。

これを用いると非常に簡単に実装することができます。

実装例 (C++)