Earliest Exact Error Engineering

解説

前問より、条件を満たす順列が存在するための必要十分条件は、$K$ が偶数かつ $K\leq\left\lfloor N^2/2\right\rfloor$ であることが分かっています。

以下ではこの条件を満たすものとし、$R=K/2$ とします。また、長さ $n$ の順列で作れる $R$ の最大値を $F(n)=\left\lfloor n^2/4\right\rfloor$ とします。

恒等順列のまま残す接頭辞

辞書順を最小にするためには、先頭から可能な限り $P_i=i$ とするべきです。

$R=0$ の場合、答えは恒等順列 $(1,2,\ldots,N)$ です。

$R>0$ の場合、$F(m)\geq R$ を満たす最小の整数 $m$ を求めます。

前問の構築より、長さ $m$ の順列だけで任意の $0$ 以上 $F(m)$ 以下の値を作れます。そのため、先頭の $N-m$ 要素を

$$P_i=i\qquad(1\leq i\leq N-m)$$

としても、残りの $m$ 要素で $R$ を作れます。

一方、先頭の $N-m+1$ 要素まで恒等順列にすると、残る要素数は $m-1$ です。$m$ の最小性より $F(m-1)<R$ なので、残りだけで $R$ を作ることはできません。

したがって、辞書順最小の順列では、先頭の $N-m$ 要素が恒等順列となり、その次の位置で初めて恒等順列と異なります。

以下では、残りの位置と値をそれぞれ $1,2,\ldots,m$ に置き換え、長さ $m$ の順列 $A$ を構築します。

先頭の値

$A_1=x$ とします。

$A$ から先頭の $x$ を取り除き、残った値のうち $x$ より大きいものを $1$ 減らすと、長さ $m-1$ の順列 $B$ が得られます。

$A_1=x$ が正の差に与える寄与は $x-1$ です。また、残りの部分の寄与は $B$ の寄与以下なので、

$$R\leq x-1+F(m-1)$$

である必要があります。

よって、$x$ は少なくとも $R-F(m-1)+1$ です。辞書順を最小にするため、

$$d=R-F(m-1),\qquad x=d+1$$

とします。

$m$ の最小性より $d\geq1$ です。また、$R\leq F(m)$ なので、$d\leq F(m)-F(m-1)=\left\lfloor m/2\right\rfloor$ です。

残りの要素の並べ方

$q=\left\lceil m/2\right\rceil$ とします。

長さ $m$ の順列 $A$ を次のように構築します。

1. 最初に $x$ を置く。
2. まだ使っていない $q+1,q+2,\ldots,m$ を昇順に置く。
3. 残っている値を昇順に置く。

例えば、$m=7,\ x=3$ なら、

$$A=(3,5,6,7,1,2,4)$$

となります。

最後に、各要素へ $N-m$ を加え、先頭の恒等順列の後ろに連結します。

スコアの確認

まず、$A_1=x$ による寄与は $x-1=d$ です。

$x\leq q$ の場合、値 $q+1,q+2,\ldots,m$ は位置 $2,3,\ldots,m-q+1$ に置かれます。

$m=2t$ のときは、これら $t$ 個の値がそれぞれ $t-1$ ずつ寄与するため、合計は $t(t-1)=F(m-1)$ です。

$m=2t+1$ のときは、これら $t$ 個の値がそれぞれ $t$ ずつ寄与するため、合計は $t^2=F(m-1)$ です。

残りの値は、それぞれの位置以下なので正の寄与を持ちません。したがって、全体の寄与は $d+F(m-1)=R$ です。

$x>q$ となる可能性があるのは、$m=2t,\ x=t+1$ の場合だけです。このとき $d=t$ であり、$R=F(m)$ です。構築される順列は

$$A=(t+1,t+2,\ldots,2t,1,2,\ldots,t)$$

であり、長さ $m$ の順列の最大値 $F(m)$ を達成します。

よって、いずれの場合も $S(P)=2R=K$ です。

辞書順最小性

長さ $n$ の順列で $F(n)$ を達成するもののうち、辞書順最小の順列は

$$\left( \left\lfloor\frac n2\right\rfloor+1, \left\lfloor\frac n2\right\rfloor+2, \ldots,n, 1,2,\ldots, \left\lfloor\frac n2\right\rfloor \right)$$

です。

実際、最大値を達成するには、前半の位置に大きい方の値を置く必要があります。その条件を満たす中で辞書順を最小にするには、前半と後半をそれぞれ昇順に並べればよいです。

$x\leq q$ の場合、$A$ から先頭の $x$ を除いて値を詰めると、長さ $m-1$ の最大値を達成する辞書順最小の順列になります。

したがって、先頭の値を最小の $x$ にした上で、残りの部分も辞書順最小です。

$x=q+1$ の場合は $R=F(m)$ なので、構築した $A$ 自体が長さ $m$ の最大値を達成する辞書順最小の順列です。

以上より、構築した順列は $S(P)=K$ を満たす順列のうち辞書順最小です。

計算量

$m$ は $1$ から順に調べても全体で $O(N)$ 時間で求められます。順列の構築にも $O(N)$ 時間かかるため、全体の計算量は $O(N)$ です。