Problem:


バブルソート(Bubble Sort)

バブルソートとは，列をソートするアルゴリズムの 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  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 ≤ 100 000      数列 A の長さ

1 ≤ Ai ≤ 1 000 000 000     数列 A に含まれる数字の大きさ

入力

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

 1 行目には，整数 N が書かれている．N は数列 A の長さを表す．

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

出力

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

採点基準

採点用データのうち，配点の10%分については，N ≤ 1 000 を満たし，任意の i, j (1 ≤ i < j ≤ N) について Ai &ne; Aj を満たす．

採点用データのうち，配点の30%分については，N ≤ 5 000 を満たし，任意の i, j (1 ≤ i < j ≤ N) について Ai &ne; Aj を満たす．

採点用データのうち，配点の80%分については，任意の i, j (1 ≤ i < j ≤ N) について Ai &ne; Aj を満たす．

入出力例

入力例 1

5
10
3
6
8
1

 出力例 1

0

数列 A の最初の 10 と最後の 1 を交換することにすると，数列 A' はソート済みの列となり，バブルソートの交換回数は 0 となる．

入力例 2

5
3
1
7
9
5

出力例 2

2

数列 A の 3 番目の 7 と最後の 5 を交換することで，数列 A' は 3,1,5,9,7 となる．A' のバブルソートによる交換回数は 2 である．

入力例 3

3
1
2
3

出力例 3

1

最初から数列 A がソートされている場合でも，数列 A' を作る際に交換を行わなければならない．

問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
5
10
3
6
8
1


Sample output:
0

Submission status: Wrong Answer

Solution code:
# coding: utf-8

# ???????????¨??????????????§????????°??¨????????´????????????
def search_max_and_2nd_value_position(numbers):
    max_position = (-1, -1)
    second_max_position = (-1, -1)
    index = 0
    for value in numbers:
        if max_position[1] < value:
            max_position = (index, value)
        index += 1
    index = 0
    for value in numbers:
        if second_max_position[1] < value and value < max_position[1]:
            second_max_position = (index, value)
        index += 1
    return (max_position, second_max_position)

# ????°????????????????????????????????????§?????????????????????????????????????????????
def search_min_value_position(numbers, offset):
    min_position = (1000000000, 1000000000)
    index = offset
    for value in numbers[offset:]:
        if min_position[1] > value:
            min_position = (index, value)
        index += 1
    return min_position

# ????????????????????¨????????\??????????????°
def bubble_sort_count(numbers):
    count = 0
    for i in range(len(numbers)):
        for j in range(i + 1, len(numbers)):
            if numbers[i] > numbers[j]:
                numbers[i],numbers[j] = (numbers[j], numbers[i])
                count += 1
    return count

line_count = int(input())
numbers = [int(input()) for i in range(line_count)]
max_position, second_max_position = search_max_and_2nd_value_position(numbers)
if max_position[0] == len(numbers)-1:
    numbers[second_max_position[0]],numbers[max_position[0]] = (max_position[1], second_max_position[1])
else:
    min_position = search_min_value_position(numbers, max_position[0] + 1)
    numbers[min_position[0]],numbers[max_position[0]] = (max_position[1], min_position[1])
print(bubble_sort_count(numbers))

Submission status: Wrong Answer

Solution code:
# coding: utf-8

def search_max_and_2nd_value_position(numbers):
    max_position = (-1, -1)
    second_max_position = (-1, -1)
    index = 0
    for value in numbers:
        if max_position[1] < value:
            max_position = (index, value)
        index += 1
    index = 0
    for value in numbers:
        if second_max_position[1] < value and value < max_position[1]:
            second_max_position = (index, value)
        index += 1
    return (max_position, second_max_position)

def search_min_value_position(numbers, offset):
    min_position = (1000000000, 1000000000)
    index = offset
    for value in numbers[offset:]:
        if min_position[1] > value:
            min_position = (index, value)
        index += 1
    return min_position

def bubble_sort_count(numbers):
    count = 0
    for i in range(len(numbers)):
        for j in range(i + 1, len(numbers)):
            if numbers[i] > numbers[j]:
                numbers[i],numbers[j] = (numbers[j], numbers[i])
                count += 1
    return count

line_count = int(input())
numbers = [int(input()) for i in range(line_count)]
max_position, second_max_position = search_max_and_2nd_value_position(numbers)
if max_position[0] == len(numbers)-1:
    numbers[second_max_position[0]],numbers[max_position[0]] = (max_position[1], second_max_position[1])
else:
    min_position = search_min_value_position(numbers, max_position[0] + 1)
    numbers[min_position[0]],numbers[max_position[0]] = (max_position[1], min_position[1])
print(bubble_sort_count(numbers))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import copy

line_count = int(input())
numbers = [int(input()) for i in range(line_count)]

def make_pattern(numbers):
    all_pattern = []
    for i in range(len(numbers)-1):
        for j in range(i + 1, len(numbers)):
            pattern = copy.deepcopy(numbers)
            pattern[i],pattern[j] = (pattern[j], pattern[i])
            all_pattern.append((pattern, i, j))
    return all_pattern

def count_bubble_sort(numbers):
    count = 0
    for i in range(len(numbers)-1):
        for k in range(i + 1, len(numbers)):
            if numbers[i] > numbers[k]:
                numbers[i], numbers[k] = (numbers[k], numbers[i])
                count += 1
    return count

min_sort_count = 10000
for i in make_pattern(numbers):
    count = count_bubble_sort(i[0])
    if min_sort_count > count:
        min_sort_count = count
print(count)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import copy

def count_sort_count(numbers):
    count = 0
    for index_of_a in range(len(numbers)-1):
        for index_of_b in range(index_of_a + 1, len(numbers)):
            if numbers[index_of_a] > numbers[index_of_b]:
                numbers[index_of_a], numbers[index_of_b] = (numbers[index_of_b], numbers[index_of_a])
                count += 1
    return count, numbers

def different_positions(answer, numbers):
    different_positions = [-1 for index in range(len(numbers))]
    index = 0
    for answer_value in answer:
        for position in range(len(numbers)):
            if numbers[position] == answer_value:
                different_positions[index] = abs(index - position)
        index += 1
    return different_positions

def find_best_swap_position(answer, numbers, max_different_position):
    min_sum = 1000000
    min_pattern = None
    for i in range(len(numbers)):
        if i != max_different_position:
            pattern = copy.deepcopy(numbers)
            pattern[i], pattern[max_different_position] = (pattern[max_different_position], pattern[i])
            sum_different = sum(different_positions(answer, pattern))
            if min_sum > sum_different:
                min_sum = sum_different
                min_pattern = pattern
    return min_pattern

line_count = int(input())
numbers = [int(input()) for count in range(line_count)]
base_sort_count, answer = count_sort_count(copy.deepcopy(numbers))
if base_sort_count == 0:
    print(1)
elif base_sort_count == 1:
    print(0)
else:
    differents = different_positions(answer, numbers)
    max_different_position = differents.index(max(differents))
    swaped = find_best_swap_position(answer, numbers, max_different_position)
    print(count_sort_count(swaped)[0])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import copy

def count_sort_count(numbers):
    count = 0
    for index_of_a in range(len(numbers)-1):
        for index_of_b in range(index_of_a + 1, len(numbers)):
            if numbers[index_of_a] > numbers[index_of_b]:
                numbers[index_of_a], numbers[index_of_b] = (numbers[index_of_b], numbers[index_of_a])
                count += 1
    return count, numbers

def different_positions(answer, numbers):
    different_positions = [-1 for index in range(len(numbers))]
    index = 0
    for answer_value in answer:
        for position in range(len(numbers)):
            if numbers[position] == answer_value:
                different_positions[index] = abs(index - position)
        index += 1
    return different_positions

def find_best_swap_position(answer, numbers, max_different_position):
    min_sum = 1000000
    min_pattern = None
    for i in range(len(numbers)):
        if i != max_different_position:
            pattern = copy.deepcopy(numbers)
            pattern[i], pattern[max_different_position] = (pattern[max_different_position], pattern[i])
            sum_different = sum(different_positions(answer, pattern))
            if min_sum > sum_different:
                min_sum = sum_different
                min_pattern = pattern
    return min_pattern

line_count = int(input())
numbers = [int(input()) for count in range(line_count)]
base_sort_count, answer = count_sort_count(copy.deepcopy(numbers))
if base_sort_count == 0:
    print(1)
else:
    differents = different_positions(answer, numbers)
    max_different_position = differents.index(max(differents))
    swaped = find_best_swap_position(answer, numbers, max_different_position)
    print(count_sort_count(swaped)[0])

Submission status: Time Limit Exceeded

Solution code:
import copy

def count_sort_count(numbers):
    count = 0
    for index_of_a in range(len(numbers)-1):
        for index_of_b in range(index_of_a + 1, len(numbers)):
            if numbers[index_of_a] > numbers[index_of_b]:
                numbers[index_of_a], numbers[index_of_b] = (numbers[index_of_b], numbers[index_of_a])
                count += 1
    return count, numbers

def different_positions(answer, numbers):
    different_positions = [-1 for index in range(len(numbers))]
    index = 0
    for answer_value in answer:
        for position in range(len(numbers)):
            if numbers[position] == answer_value:
                different_positions[index] = abs(index - position)
        index += 1
    return different_positions

def find_best_swap_position(answer, numbers, max_different_position):
    min_sum = 1000000
    min_pattern = None
    for i in range(len(numbers)):
        if i != max_different_position:
            pattern = copy.deepcopy(numbers)
            pattern[i], pattern[max_different_position] = (pattern[max_different_position], pattern[i])
            sum_different = sum(different_positions(answer, pattern))
            if min_sum > sum_different:
                min_sum = sum_different
                min_pattern = pattern
    return min_pattern

numbers = [-1 for i in range(int(input()))]
numbers = list(map(lambda x: int(input()), numbers))
base_sort_count, answer = count_sort_count(copy.deepcopy(numbers))
if base_sort_count == 0:
    print(1)
else:
    differents = different_positions(answer, numbers)
    max_different_position = differents.index(max(differents))
    swaped = find_best_swap_position(answer, numbers, max_different_position)
    print(count_sort_count(swaped)[0])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import copy

def count_sort_count(numbers):
    count = 0
    for index_of_a in range(len(numbers)-1):
        for index_of_b in range(index_of_a + 1, len(numbers)):
            if numbers[index_of_a] > numbers[index_of_b]:
                numbers[index_of_a], numbers[index_of_b] = (numbers[index_of_b], numbers[index_of_a])
                count += 1
    return count, numbers

def different_positions(answer, numbers):
    different_positions = [-1 for index in range(len(numbers))]
    index = 0
    for answer_value in answer:
        for position in range(len(numbers)):
            if numbers[position] == answer_value:
                different_positions[index] = abs(index - position)
        index += 1
    return different_positions

def find_best_swap_position(answer, numbers, differents, max_different_position):
    min_sum = 1000000
    min_pattern = None
    for i in range(len(numbers)):
        if differents[i] == 0:
            continue
        if i != max_different_position:
            pattern = copy.deepcopy(numbers)
            pattern[i], pattern[max_different_position] = (pattern[max_different_position], pattern[i])
            sum_different = sum(different_positions(answer, pattern))
            if min_sum > sum_different:
                min_sum = sum_different
                min_pattern = pattern
    return min_pattern

numbers = [-1 for i in range(int(input()))]
numbers = list(map(lambda x: int(input()), numbers))
base_sort_count, answer = count_sort_count(copy.deepcopy(numbers))
if base_sort_count == 0:
    print(1)
else:
    differents = different_positions(answer, numbers)
    max_different_position = differents.index(max(differents))
    swaped = find_best_swap_position(answer, numbers, differents, max_different_position)
    print(count_sort_count(swaped)[0])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import copy

def count_sort_count(numbers):
    count = 0
    for index_of_a in range(len(numbers)-1):
        for index_of_b in range(index_of_a + 1, len(numbers)):
            if numbers[index_of_a] > numbers[index_of_b]:
                numbers[index_of_a], numbers[index_of_b] = (numbers[index_of_b], numbers[index_of_a])
                count += 1
    return count, numbers

def different_positions(answer, numbers):
    different_positions = [index for index in range(len(numbers))]
    different_positions = list(map(lambda x: abs(answer.index(numbers[x]) - x), different_positions))
    return different_positions

def find_best_swap_position(answer, numbers, differents, max_different_position):
    min_sum = 1000000
    min_pattern = None
    for i in range(len(numbers)):
        if differents[i] == 0:
            continue
        if i != max_different_position:
            pattern = copy.deepcopy(numbers)
            pattern[i], pattern[max_different_position] = (pattern[max_different_position], pattern[i])
            sum_different = sum(different_positions(answer, pattern))
            if min_sum > sum_different:
                min_sum = sum_different
                min_pattern = pattern
    return min_pattern

numbers = [-1 for i in range(int(input()))]
numbers = list(map(lambda x: int(input()), numbers))
base_sort_count, answer = count_sort_count(copy.deepcopy(numbers))
if base_sort_count == 0:
    print(1)
else:
    differents = different_positions(answer, numbers)
    max_different_position = differents.index(max(differents))
    swaped = find_best_swap_position(answer, numbers, differents, max_different_position)
    print(count_sort_count(swaped)[0])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import copy

def count_sort_count(numbers):
    count = 0
    for index_of_a in range(len(numbers)-1):
        for index_of_b in range(index_of_a + 1, len(numbers)):
            if numbers[index_of_a] > numbers[index_of_b]:
                numbers[index_of_a], numbers[index_of_b] = (numbers[index_of_b], numbers[index_of_a])
                count += 1
    return count, numbers

def different_positions(answer, numbers):
    different_positions = [index for index in range(len(numbers))]
    return list(map(lambda x: abs(answer.index(numbers[x]) - x), different_positions))

def find_best_swap_position(answer, numbers, differents, max_different_position):
    min_sum = 1000000
    min_pattern = None
    for i in range(len(numbers)):
        if differents[i] == 0:
            continue
        if i != max_different_position:
            pattern = copy.deepcopy(numbers)
            pattern[i], pattern[max_different_position] = (pattern[max_different_position], pattern[i])
            sum_different = sum(different_positions(answer, pattern))
            if min_sum > sum_different:
                min_sum = sum_different
                min_pattern = pattern
    return min_pattern

numbers = [-1 for i in range(int(input()))]
numbers = list(map(lambda x: int(input()), numbers))
answer = sorted(numbers)

differents = different_positions(answer, numbers)
if sum(differents) == 0:
    print(1)
else:
    max_different_position = differents.index(max(differents))
    swaped = find_best_swap_position(answer, numbers, differents, max_different_position)
    print(count_sort_count(swaped)[0])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import copy

def count_sort_count(numbers):
    count = 0
    for index_of_a in range(len(numbers)-1):
        for index_of_b in range(index_of_a + 1, len(numbers)):
            if numbers[index_of_a] > numbers[index_of_b]:
                numbers[index_of_a], numbers[index_of_b] = (numbers[index_of_b], numbers[index_of_a])
                count += 1
    return count, numbers

def different_positions(answer, numbers):
    different_positions = [index for index in range(len(numbers))]
    return list(map(lambda x: abs(answer.index(numbers[x]) - x), different_positions))

def find_best_swap_position(answer, numbers, differents, max_different_position):
    min_sum = 1000000
    min_pattern = None
    for i in range(len(numbers)):
        if differents[i] <= 1:
            continue
        if i != max_different_position:
            pattern = copy.deepcopy(numbers)
            pattern[i], pattern[max_different_position] = (pattern[max_different_position], pattern[i])
            sum_different = sum(different_positions(answer, pattern))
            if min_sum > sum_different:
                min_sum = sum_different
                min_pattern = pattern
    return min_pattern

numbers = [-1 for i in range(int(input()))]
numbers = list(map(lambda x: int(input()), numbers))
answer = sorted(numbers)

differents = different_positions(answer, numbers)
if sum(differents) == 0:
    print(1)
else:
    max_different_position = differents.index(max(differents))
    swaped = find_best_swap_position(answer, numbers, differents, max_different_position)
    print(count_sort_count(swaped)[0])

Submission status: Time Limit Exceeded

Solution code:
import copy
def main():
    N = int(input())
    A = []
    for _ in range(N):
        A.append(int(input()))

    A_s = sorted(A)   #A_sorted

    n = 0
    for x in range(N):
        n += (N - 1) - x

    B = []
    for x in range(N - 1):
        for y in range(x + 1, N):
            hoge = copy.deepcopy(A)
            tmp = hoge[x]
            hoge[x] = hoge[y]
            hoge[y] = tmp
            B.append(hoge)

    Ans = []
    for x in range(len(B)):
        cnt = 0
        for _ in range(N - 1):
            for y in range(N - 1):
                if B[x] == A_s:
                    break
                elif B[x][y] > B[x][y + 1]:
                    cnt += 1
                    tmp = B[x][y]
                    B[x][y] = B[x][y + 1]
                    B[x][y + 1] = tmp
        Ans.append(cnt)

    Ans.sort()
    print(Ans[0])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
def main():
    N = int(input())
    A = []
    for _ in range(N):
        A.append(int(input()))

    A_s = sorted(A)   #A_sorted

    n = 0
    for x in range(N):
        n += (N - 1) - x

    B = []
    for x in range(N - 1):
        for y in range(x + 1, N):
            hoge = copy.deepcopy(A)
            tmp = hoge[x]
            hoge[x] = hoge[y]
            hoge[y] = tmp
            B.append(hoge)

    Ans = []
    for x in range(len(B)):
        cnt = 0
        for _ in range(N - 1):
            for y in range(N - 1):
                if B[x] == A_s:
                    break
                elif B[x][y] > B[x][y + 1]:
                    cnt += 1
                    tmp = B[x][y]
                    B[x][y] = B[x][y + 1]
                    B[x][y + 1] = tmp
        if len(Ans) == 0:
            Ans.append(cnt)
        else:
            if Ans[0] > cnt:
                Ans[0] = cnt

    print(Ans[0])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
def main():
    N = int(input())
    A = []
    for _ in range(N):
        A.append(int(input()))

    A_s = sorted(A)   #A_sorted

    B = []
    for x in range(N - 1):
        for y in range(x + 1, N):
            hoge = copy.deepcopy(A)
            tmp = hoge[x]
            hoge[x] = hoge[y]
            hoge[y] = tmp
            B.append(hoge)

    Ans = []
    for x in range(len(B)):
        cnt = 0
        for _ in range(N - 1):
            for y in range(N - 1):
                if B[x] == A_s:
                    break
                elif B[x][y] > B[x][y + 1]:
                    cnt += 1
                    tmp = B[x][y]
                    B[x][y] = B[x][y + 1]
                    B[x][y + 1] = tmp
        if len(Ans) == 0:
            Ans.append(cnt)
        else:
            if Ans[0] > cnt:
                Ans[0] = cnt

    print(Ans[0])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
def main():
    N = int(input())
    A = []
    for _ in range(N):
        A.append(int(input()))

    A_s = sorted(A)   #A_sorted

    B = []
    for x in range(N - 1):
        for y in range(x + 1, N):
            hoge = copy.deepcopy(A)
            tmp = hoge[x]
            hoge[x] = hoge[y]
            hoge[y] = tmp
            B.append(hoge)

    Ans = []
    for x in range(len(B)):
        cnt = 0
        for _ in range(N - 1):
            if B[x] == A_s:
                break
            for y in range(N - 1):
                if B[x] == A_s:
                    break
                elif B[x][y] > B[x][y + 1]:
                    cnt += 1
                    tmp = B[x][y]
                    B[x][y] = B[x][y + 1]
                    B[x][y + 1] = tmp
        if len(Ans) == 0:
            Ans.append(cnt)
        else:
            if Ans[0] > cnt:
                Ans[0] = cnt

    print(Ans[0])

if __name__ == "__main__":
    main()