バブルソートとは,列をソートするアルゴリズムの 1 つである.長さ N の数列 A を昇順にソートしたいとしよう.バブルソートは,隣り合う 2 つの数で大小関係が崩れているものがあれば,それらの位置を交換する.これを,数列を前から順に走査しながら行う.すなわち,Ai > Ai+1 となっている場所があれば,その 2 数を交換するということを,i = 1, 2, ... , 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つの整数は必ずしも隣り合っている必要はないことに注意せよ.)
標準入力から以下のデータを読み込め.
標準出力に,数列 A' のバブルソートによる交換回数の最小値を表す整数を 1 行で出力せよ.
5 10 3 6 8 1
0
数列 A の最初の 10 と最後の 1 を交換することにすると,数列 A' はソート済みの列となり,バブルソートの交換回数は 0 となる.
5 3 1 7 9 5
2
数列 A の 3 番目の 7 と最後の 5 を交換することで,数列 A' は 3,1,5,9,7 となる.A' のバブルソートによる交換回数は 2 である.
3 1 2 3
1
最初から数列 A がソートされている場合でも,数列 A' を作る際に交換を行わなければならない.
問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。