DOJ Starter Contest 1 I - 수열 정렬하기 5
- サイト
- DOJ
- コンテスト
- DOJ Starter Contest 1
- 問題
- I - 수열 정렬하기 5
数列 の「整列度」を、 かつ を満たす組 の個数とします。隣り合う要素の交換をちょうど 回行った後の整列度を最大化し、その値と交換手順を出力する問題です(、)。
逆転している隣接要素を交換する
Section titled “逆転している隣接要素を交換する”隣り合う 要素を交換しても、それ以外の要素との前後関係は変わりません。よって、整列度の変化は交換する 要素の関係だけで決まります。
- 左の要素が大きい場合は、整列度が 増える。
- 左の要素が小さい場合は、整列度が 減る。
- 同じ値の場合は、整列度は変わらない。
したがって、まずは左の要素が大きい隣接対を交換します。数列が整列済みでなければそのような場所は必ず存在するので、整列するまでは毎回 ずつ増やせます。 回で より大きく増やすことはできないため、これが最適です。
コードではバブルソートの走査を 回行い、交換回数が残っている間だけ逆転した隣接対を交換しています。 回を使い切った場合は、その状態が答えになります。
整列後に残った交換を消化する
Section titled “整列後に残った交換を消化する”整列しても交換回数が残っている場合、同じ値の隣接対があれば、そこで交換を繰り返します。数列も整列度も変わらないので、最大の整列度を保てます。
同じ値がない場合は、先頭の 要素を繰り返し交換します。 回交換すれば元に戻るため、残り回数が偶数なら整列済みの状態、奇数なら先頭の 組だけが逆転した状態になります。
全要素が異なる場合、隣接交換のたびに転倒数の偶奇が反転します。整列に必要な交換回数を使った後で、さらに奇数回交換して整列済みの状態に戻ることはできません。したがって、この場合の整列度が最大値より 小さくなるのは避けられず、先頭の 組だけを逆転させる方法が最適です。
答えと手順を出力する
Section titled “答えと手順を出力する”最後の数列について、条件 を満たす組を全探索して整列度を求めます。交換位置は ans に 0 始まりで保存しているので、出力時に を加えます。
バブルソートの走査と整列度の計算が 、残りの交換と手順の出力が なので、計算量は 、空間計算量は です。
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 = 0for j in range(N - 1): if A[j] == A[j + 1]: i = j breakwhile 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)