LeetCode Beautiful Array
$ 1以上の整数$ Nが与えられる。$ 1, 2, \ldots, Nを並び替えた順列であって、以下の条件を満たすものを一つ構成せよ。
配列の$ i番目$ (1 \leq i \leq N)の要素を$ a_iと表す時、任意の$ 1 \leq i \lt j \leq Nなる$ (i,j)について以下を満たす$ kが存在しない
1. $ i \lt k \lt j
2. $ 2 a_k = a_i + a_j
例:
$ n = 4
→[2, 1, 4, 3]
---
$ 1, 2, \ldots, Nの順列であって、順列からどの3要素を選んでも左から順に等差数列を成さないものを作れるか、という問題。
以下の解答が見事だったのでその翻訳。
---
前提として以下が得られる。
1. $ a_iと$ a_jの偶奇が異なる時、2 番目の条件の左辺が偶数で右辺が奇数となるため、条件を満たす$ kは存在しない
2. 条件を満たす配列の全要素を$ A$ (\neq 0)倍しても条件を満たしたままである
$ 2a_k = a_i + a_j \iff 2Aa_k = Aa_i + Aa_j であることからわかる
3. 条件を満たす配列の全要素に$ Bを足しても条件を満たしたままである
$ 2a_k = a_i + a_j \iff 2(a_k + B) = (a_i + B) + (a_j + B)であることからわかる
4. 条件を満たす配列からどの要素を取り除いても、満たすべき条件が減るのみであるため条件を満たしたままである
条件を満たす$ 1, 2, \ldots, nの順列があるとする。上記前提の 2, 3 から、これに対して以下の操作を行って得た配列は条件を満たす。
a. 全要素を 2 倍する
$ 2, 4, \ldots, 2nが含まれる
b. 全要素を 2 倍して 1 引く
$ 1, 3, \ldots, 2n-1が含まれる
前提の 1 から、 a の配列の後ろに b の配列を繋げたものは条件を満たす。これは$ 1, 2, \ldots 2nの順列となる。
長さ 1 で条件を満たす順列である[1]に対してこの操作を繰り返すことで、長さ$ N以上の条件を満たす順列が作れる。前提の 4 から、この順列から$ N+1以上の要素を取り除くことで、条件を満たす$ 1, 2, \ldots, Nの順列が得られる。