[1] 必要条件

解が存在するためには，\(N\geq 2K\) が必要です．実際，\(1\leq A_K\leq N\) かつ \(|A_K-K| \geq K\) を満たすように\(A_K\) がとれるためには \(N\geq 2K\) が必要です．

以下では，この必要条件のもとで解が存在することを確かめます．

---

[2] 上手くいかない貪欲アルゴリズム

辞書順最小化に関する問題なので，次のような貪欲アルゴリズムが考えられます．

\(i=1,2,3,\ldots\) の順に次を行う：\(A_1, \ldots, A_{i-1}\) に現れていない数 \(x\) のうち，\(\lvert x - i\rvert \geq K\) を満たす最小の整数 \(x\) を \(A_i\) とする．

この貪欲アルゴリズムは失敗します．実際「入力例 2」では，\(x = 1\) が \(\lvert x - 4\rvert\geq 3\) を満たすにも関わらず，最適解は \(A_4 = 7\) を選択しています．この理由を考えてみましょう．

順列を構成するにあたって，すべての \(i\) に対して \(A_i\) を定めなければいけないのはもちろんのことですが，逆にすべての \(x\) に対して \(A_i = x\) となる \(i\) を定めなければいけないことに注目します．例えば 「入力例 2」では \(A_i = 7\) となる \(i\) に注目すると，\(i\leq 4\) を満たす必要があります．これで，「入力例2」の最適解において \(A_4 = 7\) としなくてはならない理由が説明できそうです．

---

[3] 上手くいく貪欲アルゴリズム

[2] での失敗を反省を生かして，次のような貪欲アルゴリズムを考えます．

\(i=1,2,3,\ldots\) の順に次を行う：

• \(j = i+K\) が \(A_1, \ldots, A_{i-1}\) に現れておらず，\(j > N - K\) であるならば，\(A_i = j\) とする．
• それ以外の場合には，\(A_1, \ldots, A_{i-1}\) に現れていない数 \(x\) のうち，\(\lvert x - i\rvert \geq K\) を満たす最小の整数 \(x\) を \(A_i\) とする．

このアルゴリズムで順列が定まること（つまり，条件を満たす \(x\) がとれないということが起こらないこと）は明らかではありませんが，順列が定まるならば [2] の議論によりそれが最適解です．

---

[4] 貪欲アルゴリズムの結果

[3] のアルゴリズムにより順列が定まることを確かめましょう．

まず \(2K\leq N\leq 4K\) のときにはアルゴリズムによって次のような順列 \(A\) が得られることが確かめられます．

\(2K\leq N\leq 3K\) の場合

\[ A_i = \begin{cases} i + K & (1\leq i \leq N-K) \\ i - N + K & (N-K < i\leq N) \end{cases} \]

\(3K < N \leq 4K\) の場合

\[ A_i = \begin{cases} i+K &(1\leq i \leq K)\\ i-K &(K<i\leq N-2K)\\ i + K &(N-2K< i\leq N-K)\\ i-2K &(N-K < i \leq 3K)\\ i-K &(3K < i \leq N) \end{cases} \]

\(N\geq 4K\) の場合も，はじめの \(2K\) 項に \((K+1, \ldots, 2K, 1, \ldots, K)\) 並んだあと \(N-2K\) の場合と同様の動作をすることから，帰納的に [3] のアルゴリズムが解を出力することが分かります．

[3] のアルゴリズムを適切に実装する，あるいは上述の数式を利用することで，本問題は \(O(N)\) 時間で解くことができます．

---

[5] 参考：\(K=4\) の場合の解

例えば \(K = 4\) のとき，解は次のようになります．

• \(N=8\)：\((5,6,7,8,1,2,3,4)\)
• \(N=9\)：\((5,6,7,8,9,1,2,3,4)\)
• \(N=10\)：\((5,6,7,8,9,10,1,2,3,4)\)
• \(N=11\)：\((5,6,7,8,9,10,11,1,2,3,4)\)
• \(N=12\)：\((5,6,7,8,9,10,11,12,1,2,3,4)\)
• \(N=13\)：\((5,6,7,8,1,10,11,12,13,2,3,4,9)\)
• \(N=14\)：\((5,6,7,8,1,2,11,12,13,14,3,4,9,10)\)
• \(N=15\)：\((5,6,7,8,1,2,3,12,13,14,15,4,9,10,11)\)
• \(N=16\)：\((5,6,7,8,1,2,3,4,13,14,15,16,9,10,11,12)\)
• \(N=17\)：\((5,6,7,8,1,2,3,4,13,14,15,16,17,9,10,11,12)\)
• \(\vdots\)