コンテンツにスキップ

DOJ Beginner Contest 8 E - Swap Two Elements

サイト
DOJ
コンテスト
DOJ Beginner Contest 8
問題
E - Swap Two Elements

長さ NN の順列 AA が与えられます。次の操作を何回でも行えます。

  • 1≤i<j≤N1 \le i < j \le N を選ぶ。Ai,Ai+1,…,AjA_i, A_{i+1}, \dots, A_j のうち最小の要素と 2 番目に小さい要素の位置を入れ替える。

AA を昇順にするための操作回数の最小値と、その回数を達成する操作の列を 1 つ出力する問題です。NN の総和は 10001000 以下です。

答えは AA の転倒数(位置が前なのに値が大きい組 (p,q)(p, q) の個数)です。

1 回の操作で転倒数は 1 しか変わらない

Section titled “1 回の操作で転倒数は 1 しか変わらない”

区間 [i,j][i, j] で入れ替える 2 つの値を x<yx < y、その位置を p<qp < q とします。

  • 区間内の pp と qq の間にある要素は、どれも xx と yy より大きいです(x,yx, y が区間で最も小さい 2 つだからです)。pp と qq の間にある要素から見ると、xx と yy はどちらも自分より小さいままです。そのため、この要素が関わる転倒の数は、入れ替えても変わりません。
  • pp より前、qq より後ろの要素から見ても、xx と yy の両方が同じ側にあることは変わらないので、転倒の数は変わりません。

変わるのは xx と yy の組だけで、転倒数はちょうど 11 増えるか 11 減ります。昇順の順列の転倒数は 00 なので、操作は転倒数の回数以上必要です。

隣どうしの入れ替えで達成できる

Section titled “隣どうしの入れ替えで達成できる”

j=i+1j = i + 1 とすると、区間は Ai,Ai+1A_i, A_{i+1} の 2 つだけなので、この操作は隣どうしの入れ替えです。バブルソートのように、Ai>Ai+1A_i > A_{i+1} となっている隣の組を入れ替えるたびに、転倒数は 11 ずつ減ります。したがって、ちょうど転倒数の回数で昇順にできます。

NN の総和が 10001000 以下なので、O(N2)O(N^2) のバブルソートで十分間に合います。

Python
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
ans = []
for _ in range(N):
for i in range(1, N):
if A[i - 1] > A[i]:
ans.append((i - 1, i))
A[i - 1], A[i] = A[i], A[i - 1]
print(len(ans))
for x, y in ans:
print(x + 1, y + 1)

バブルソートを行い、入れ替えた隣の組 (i,i+1)(i, i+1) を記録して出力しています。