解説
判定
まず、任意の順列 P について S(P) は偶数です。
整数 x について ∣x∣≡x(mod2) なので、
S(P)≡i=1∑N(Pi−i)≡i=1∑NPi−i=1∑Ni≡0(mod2)
が成り立ちます。
次に、S(P) の最大値を求めます。
Pi>i を満たす添字の集合を U とし、∣U∣=m とします。∑i=1N(Pi−i)=0 であるため、
S(P)=2i∈U∑(Pi−i)
と表せます。
m 個の Pi の和は、大きい方から m 個を選んだ場合以下です。また、m 個の添字 i の和は、小さい方から m 個を選んだ場合以上です。したがって、
i∈U∑(Pi−i)≤i=N−m+1∑Ni−i=1∑mi=m(N−m)
です。
m(N−m) の最大値は ⌊N2/4⌋ なので、
S(P)≤2⌊4N2⌋=⌊2N2⌋
となります。
よって、K が奇数、または K>⌊N2/2⌋ なら、条件を満たす順列は存在しません。
以下では、K が偶数かつ K≤⌊N2/2⌋ なら、必ず構築できることを示します。
構築
はじめ、P=(1,2,…,N) とします。また、作るべきスコアの半分を R=K/2 とします。
まだ変更していない区間の左端を l、右端を r とします。最初は l=1, r=N です。
位置 l と位置 r はまだ変更されていないため、Pl=l, Pr=r です。これらを入れ替えると、この2要素のスコアへの寄与は
∣r−l∣+∣l−r∣=2(r−l)
となります。
そこで、次の操作を繰り返します。
- R≥r−l なら、Pl と Pr を入れ替え、R から r−l を引く。その後、l を 1 増やし、r を 1 減らす。
- 0<R<r−l なら、Pl と Pl+R を入れ替えて終了する。
- R=0 なら、そのまま終了する。
最後の場合、位置 l と位置 l+R の入れ替えによって増えるスコアは 2R なので、残っているスコアをちょうど作れます。
正当性
この構築が条件を満たすことを示します。
外側から位置 l,r を入れ替えた後は、その2位置を以降の操作で使用しません。そのため、各入れ替えで変化する位置は互いに異なり、それぞれのスコアへの寄与を独立に足し合わせることができます。
位置 l,r の入れ替えではスコアが 2(r−l) 増え、R をちょうど r−l 減らしています。また、最後に位置 l,l+R を入れ替える場合は、スコアがちょうど 2R 増えます。
したがって、終了時に作られたスコアは最初の 2R=K と一致します。
あとは、途中で使用できる位置がなくなる前に R=0 になることを示します。
外側からすべての組を入れ替えたとき、入れ替える位置間の距離の総和は
- N=2m のとき、(2m−1)+(2m−3)+⋯+1=m2
- N=2m+1 のとき、2m+(2m−2)+⋯+2=m(m+1)
です。
どちらの場合も、この値は ⌊N2/4⌋ です。仮定より R=K/2≤⌊N2/4⌋ なので、構築に必要な距離の合計は十分に存在します。
以上より、K が偶数かつ K≤⌊N2/2⌋ なら、スコアがちょうど K となる順列を必ず構築できます。
したがって、条件を満たす順列が存在するための必要十分条件は、K が偶数かつ K≤⌊N2/2⌋ であることです。
計算量
各位置を高々一度しか操作しないため、計算量は O(N) です。
