コンテンツにスキップ

DOJ Starter Contest 1 I - 수열 정렬하기 5

サイト
DOJ
コンテスト
DOJ Starter Contest 1
問題
I - 수열 정렬하기 5

数列 AA の「整列度」を、i<ji<j かつ Ai<AjA_i<A_j を満たす組 (i,j)(i,j) の個数とします。隣り合う要素の交換をちょうど KK 回行った後の整列度を最大化し、その値と交換手順を出力する問題です(2≤N≤10002\le N\le1000、0≤K≤5×1050\le K\le5\times10^5)。

逆転している隣接要素を交換する

Section titled “逆転している隣接要素を交換する”

隣り合う 22 要素を交換しても、それ以外の要素との前後関係は変わりません。よって、整列度の変化は交換する 22 要素の関係だけで決まります。

  • 左の要素が大きい場合は、整列度が 11 増える。
  • 左の要素が小さい場合は、整列度が 11 減る。
  • 同じ値の場合は、整列度は変わらない。

したがって、まずは左の要素が大きい隣接対を交換します。数列が整列済みでなければそのような場所は必ず存在するので、整列するまでは毎回 11 ずつ増やせます。11 回で 11 より大きく増やすことはできないため、これが最適です。

コードではバブルソートの走査を NN 回行い、交換回数が残っている間だけ逆転した隣接対を交換しています。KK 回を使い切った場合は、その状態が答えになります。

整列後に残った交換を消化する

Section titled “整列後に残った交換を消化する”

整列しても交換回数が残っている場合、同じ値の隣接対があれば、そこで交換を繰り返します。数列も整列度も変わらないので、最大の整列度を保てます。

同じ値がない場合は、先頭の 22 要素を繰り返し交換します。22 回交換すれば元に戻るため、残り回数が偶数なら整列済みの状態、奇数なら先頭の 11 組だけが逆転した状態になります。

全要素が異なる場合、隣接交換のたびに転倒数の偶奇が反転します。整列に必要な交換回数を使った後で、さらに奇数回交換して整列済みの状態に戻ることはできません。したがって、この場合の整列度が最大値より 11 小さくなるのは避けられず、先頭の 11 組だけを逆転させる方法が最適です。

最後の数列について、条件 Ai<AjA_i<A_j を満たす組を全探索して整列度を求めます。交換位置は ans に 0 始まりで保存しているので、出力時に 11 を加えます。

バブルソートの走査と整列度の計算が O(N2)O(N^2)、残りの交換と手順の出力が O(K)O(K) なので、計算量は O(N2+K)O(N^2+K)、空間計算量は O(N+K)O(N+K) です。

Python
N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = []
for _ in range(N):
for i in range(N - 1):
if K > 0 and A[i] > A[i + 1]:
A[i], A[i + 1] = A[i + 1], A[i]
K -= 1
ans.append(i)
i = 0
for j in range(N - 1):
if A[j] == A[j + 1]:
i = j
break
while K > 0:
A[i], A[i + 1] = A[i + 1], A[i]
K -= 1
ans.append(i)
print(sum(A[i] < A[j] for i in range(N - 1) for j in range(i + 1, N)))
for a in ans:
print(a + 1)