バブルソート (Bubble Sort)

バブルソートとは，列をソートするアルゴリズムの \(1\) つである．長さ \(N\) の数列 \(A\) を昇順にソートしたいとしよう．バブルソートは，隣り合う \(2\) つの数で大小関係が崩れているものがあれば，それらの位置を交換する．これを，数列を前から順に走査しながら行う．すなわち，\(A_i > A_{i + 1}\) となっている場所があれば，その \(2\) 数を交換するということを，\(i = 1, 2, \ldots, N - 1\) に対してこの順で行うのが \(1\) 回の走査である．この走査を \(N − 1\) 回繰り返すことで，数列を昇順にソートできることが知られている．

数列 \(A\) のバブルソートによる交換回数とは，数列 \(A\) に上記のアルゴリズムを適用した時に，整数の交換が行われる回数である．（バブルソートとして知られるアルゴリズム及び実装には，ループの順番や範囲，及び終了条件など，細かな差異がある場合がある．ただし，同じ数列に適用した際の整数の交換回数はそれらの差異により変化しないことが知られている．）

例えば，以下のプログラムは長さ n の整数の配列 a をバブルソートによりソートする関数を C 言語で記述したものである．

void bubble_sort(int *a, int n) {
  int i, j;
  for (i = 0; i < n - 1; ++i) {
    for (j = 0; j < n - 1; ++j) {
      if (a[j] > a[j + 1]) {
        /* 以下 3 行が 1 回の整数の交換に相当 */
        int x = a[j];
        a[j] = a[j + 1];
        a[j + 1] = x;
      }
    }
  }
}

課題

長さ \(N\) の数列 \(A\) が与えられる．数列 \(A\) の任意の場所の \(2\) つの整数を \(1\) 回だけ交換した数列 \(A'\) を作るとする．数列 \(A'\) のバブルソートによる交換回数の最小値を求めるプログラムを作成せよ．（最初に交換する \(2\) つの整数は必ずしも隣り合っている必要はないことに注意せよ．）

（注）過去問移植時に制約を修正．

標準入力から以下のデータを読み込め．

• \(1\) 行目には，整数 \(N\) が書かれている．\(N\) は数列 \(A\) の長さを表す．
• 続く \(N\) 行のうちの \(i\) 行目 (\(1 \leqq i \leqq N\)) には，整数 \(A_i\) が書かれている．これは数列 \(A\) の \(i\) 番目の整数を表す．

標準出力に，数列 \(A'\) のバブルソートによる交換回数の最小値を表す整数を \(1\) 行で出力せよ．

採点用データのうち，配点の \(10\) %分については，\(N \leqq 1 000\) を満たし，任意の \(i, j\) (\(1 \leqq i < j \leqq N\)) について \(A_i \neq A_j\) を満たす．

採点用データのうち，配点の \(30\) %分については，\(N \leqq 5\,000\) を満たし，任意の \(i, j\) (\(1 \leqq i < j \leqq N\)) について \(A_i \neq A_j\) を満たす．

採点用データのうち，配点の \(80\) %分については，任意の \(i, j\) (\(1 \leqq i < j \leqq N\)) について \(A_i \neq A_j\) を満たす．

JOI 2013 · JCIOI · CC BY-SA 4.0