コンテンツにスキップ

順列

タグ「順列」の記事 2 件

DOJ Beginner Contest 12 F - Half Shuffle

長さ 2N2N の順列 PP が与えられます。1 回の操作では、相異なる位置をちょうど NN 個選び、そこにある値を好きな順に並べ替えます。PP を昇順に並べるのに必要な操作回数の最小値を求める問題です(2≤N≤30002 \le N \le 3000、全テストケースの NN の総和は 30003000 以下)。

PP を巡回置換に分解し、長さが 22 以上のサイクルの長さを l1,…,lkl_1, \dots, l_k とします。正しい位置にない値の個数は s=l1+⋯+lks = l_1 + \dots + l_k です。答えは次のとおりです。

  • s=0s = 0 なら 00 回。
  • 1≤s≤N1 \le s \le N なら 11 回。
  • s>Ns > N で、「s<2Ns < 2N」または「いくつかのサイクルの長さの和をちょうど NN にできる」なら 22 回。
  • それ以外(s=2Ns = 2N で、和を NN にできない)なら 33 回。

1 回の操作で動かせるのは NN 個なので、1 回で済むのは s≤Ns \le N のときだけです。このときは、正しい位置にない位置をすべて選び、足りない分は正しい位置にある位置で埋めて、そのまま並べ直せば終わります。

s>Ns > N なら 2 回以上かかります。

いくつかのサイクルの長さの和がちょうど NN なら、1 回目にそれらのサイクルの位置を選んで正しく並べます。残りは s−N≤Ns - N \le N 個なので、2 回目で終わります。

s<2Ns < 2N のときも 2 回でできます。サイクルの一部を 1 回の操作で直す方法を考えます。サイクル x→Px→PPx→⋯x \to P_x \to P_{P_x} \to \cdots から、つながった rr 個の位置を選びます。そこに並ぶ値のうち r−1r - 1 個は、正しい位置が選んだ位置の中にあります。よって、この操作で r−1r - 1 個を正しい位置に置けて、サイクルの長さは r−1r - 1 だけ短くなります。1 回目では、サイクルを丸ごと選べるだけ選び、残りの rr 個の枠は次のサイクルの一部で埋めます。すると、正しい位置に置ける値は N−1N - 1 個以上になります。残りは s−(N−1)≤Ns - (N - 1) \le N 個なので、2 回目で終わります。

逆に s=2Ns = 2N のときに 2 回でできたとします。1 回目に選ばなかった NN 個の位置は、1 回目のあとも正しくないままです。2 回目で動かせるのは NN 個なので、1 回目に選んだ NN 個の位置は、1 回目ですべて正しくならなければいけません。そのためには、選んだ位置にある値の正しい位置が、すべて選んだ位置の中になければなりません。これは、選んだ位置がいくつかのサイクルの和集合であることを意味します。つまり、サイクルの長さの和をちょうど NN にできなければ、2 回ではできません。

上の「サイクルの一部を直す」方法で 1 回操作すると、残りは s−(N−1)≤N+1<2Ns - (N - 1) \le N + 1 < 2N 個になります(N≥2N \ge 2 です)。ここから 2 回で終わるので、どの場合も 3 回あれば十分です。

サイクルの長さの和を NN にできるか

Section titled “サイクルの長さの和を NNN にできるか”

部分和問題の DP で判定します。dp[j]\mathrm{dp}[j] を「いくつかのサイクルを選んで長さの和を jj にできるか」として、サイクルを 1 つずつ加えて更新します。サイクルは高々 NN 個なので、計算量は O(N2)O(N^2) です。

Python
for _ in range(int(input())):
N = int(input())
P = list(map(lambda x: int(x) - 1, input().split()))
visited = [False] * (2 * N)
l = []
for i in range(2 * N):
if visited[i]:
continue
x = i
visited[x] = True
r = [x]
while i != P[x]:
x = P[x]
visited[x] = True
r.append(x)
if len(r) > 1:
l.append(len(r))
s = sum(l)
dp = [0] * (N + 1)
dp[0] = 1
for x in l:
for i in reversed(range(x, N + 1)):
dp[i] |= dp[i - x]
if s == 0:
print(0)
elif s <= N:
print(1)
elif dp[N] or s < 2 * N:
print(2)
else:
print(3)

前半では、まだ見ていない位置 i から P をたどってサイクルを取り出し、長さが 22 以上ならその長さを l に入れています。後半の dp は部分和問題の DP で、i を大きいほうから回すことで、同じサイクルを 2 回使わないようにしています。

DOJ Beginner Contest 9 C - Yet Another Permutation Problem 2

11 から NN までの整数の順列 PP が与えられます。P1+Q1,P2+Q2,…,PN+QNP_1 + Q_1, P_2 + Q_2, \dots, P_N + Q_N が広義単調増加になるような順列 QQ を 1 つ作る問題です。答えが複数あれば、どれを出力してもかまいません。

テストケースは T≤105T \le 10^5 個あり、NN の総和は 2×1052 \times 10^5 以下です。

Qi=N+1−PiQ_i = N + 1 - P_i とします。

PP が 11 から NN の順列なので、N+1−PiN + 1 - P_i も 11 から NN までを 1 回ずつとり、QQ は順列になります。そして、どの ii でも Pi+Qi=N+1P_i + Q_i = N + 1 です。和がすべて等しいので、広義単調増加の条件を満たします。

Python
for _ in range(int(input())):
N = int(input())
P = list(map(int, input().split()))
print(*[N - p + 1 for p in P])