DOJ Beginner Contest 12 F - Half Shuffle
長さ の順列 が与えられます。1 回の操作では、相異なる位置をちょうど 個選び、そこにある値を好きな順に並べ替えます。 を昇順に並べるのに必要な操作回数の最小値を求める問題です(、全テストケースの の総和は 以下)。
を巡回置換に分解し、長さが 以上のサイクルの長さを とします。正しい位置にない値の個数は です。答えは次のとおりです。
- なら 回。
- なら 回。
- で、「」または「いくつかのサイクルの長さの和をちょうど にできる」なら 回。
- それ以外( で、和を にできない)なら 回。
1 回でできる場合
Section titled “1 回でできる場合”1 回の操作で動かせるのは 個なので、1 回で済むのは のときだけです。このときは、正しい位置にない位置をすべて選び、足りない分は正しい位置にある位置で埋めて、そのまま並べ直せば終わります。
2 回でできる場合
Section titled “2 回でできる場合”なら 2 回以上かかります。
いくつかのサイクルの長さの和がちょうど なら、1 回目にそれらのサイクルの位置を選んで正しく並べます。残りは 個なので、2 回目で終わります。
のときも 2 回でできます。サイクルの一部を 1 回の操作で直す方法を考えます。サイクル から、つながった 個の位置を選びます。そこに並ぶ値のうち 個は、正しい位置が選んだ位置の中にあります。よって、この操作で 個を正しい位置に置けて、サイクルの長さは だけ短くなります。1 回目では、サイクルを丸ごと選べるだけ選び、残りの 個の枠は次のサイクルの一部で埋めます。すると、正しい位置に置ける値は 個以上になります。残りは 個なので、2 回目で終わります。
逆に のときに 2 回でできたとします。1 回目に選ばなかった 個の位置は、1 回目のあとも正しくないままです。2 回目で動かせるのは 個なので、1 回目に選んだ 個の位置は、1 回目ですべて正しくならなければいけません。そのためには、選んだ位置にある値の正しい位置が、すべて選んだ位置の中になければなりません。これは、選んだ位置がいくつかのサイクルの和集合であることを意味します。つまり、サイクルの長さの和をちょうど にできなければ、2 回ではできません。
3 回でできること
Section titled “3 回でできること”上の「サイクルの一部を直す」方法で 1 回操作すると、残りは 個になります( です)。ここから 2 回で終わるので、どの場合も 3 回あれば十分です。
サイクルの長さの和を にできるか
Section titled “サイクルの長さの和を NNN にできるか”部分和問題の DP で判定します。 を「いくつかのサイクルを選んで長さの和を にできるか」として、サイクルを 1 つずつ加えて更新します。サイクルは高々 個なので、計算量は です。
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 をたどってサイクルを取り出し、長さが 以上ならその長さを l に入れています。後半の dp は部分和問題の DP で、i を大きいほうから回すことで、同じサイクルを 2 回使わないようにしています。