ALDS1_6の解答例(Python)

並び替えに関する問題です． アルゴリズムについて詳しく知りたい方は参考文献などをご覧ください．

1. ALDS1_6_A: Counting Sort

# ALDS1_6_A
def CountingSort(A, B, k):
    # カウント用のリストを用意する
    C = [0 for _ in range(k+1)]
    
    # C[i] に i の出現数を記録する
    n = len(A)
    for j in range(n):
        C[A[j]] += 1
    
    # C[i] に i 以下の数の出現数を記録する
    for i in range(1,k+1):
        C[i] = C[i] + C[i-1]
        
    for j in range(n):
        j = n-j-1
        B[C[A[j]]-1] = A[j]
        C[A[j]] -= 1
        
n = int(input())
A = list(map(int,input().split(" ")))
B = [0 for _ in range(n)] # 並び替え後のリスト
k = max(A) # Aの最大値が必要
CountingSort(A, B, k)

print(*B)

2. ALDS1_6_B: Partition

# ALDS1_6_B
# A[p:r] を A[r]を基準に分割する
def partition(A, p, r):
    x = A[r]
    # i = p-1 # 疑似コードはこっち
    i = p # i=pに変えた
    for j in range(p,r):
        if A[j] <= x:
            # i = i+1 # 疑似コードはこっち
            # A[i] と A[j] を交換
            tmp = A[i]
            A[i] = A[j]
            A[j] = tmp
            i = i+1 # インクリメントの起こる位置を変えた
            
    # A[i+1] と A[r] を交換 疑似コードはこっち
#     tmp = A[i+1]
#     A[i+1] = A[r]
#     A[r] = tmp
#     return i+1

    # A[i] と A[r] を交換 i(xより大きい位置)とxを最後に交換
    tmp = A[i]
    A[i] = A[r]
    A[r] = tmp
    return i

n = int(input())
A = list(map(int,input().split(" ")))
r = len(A)-1 # rは配列 A の最後の要素を指す添え字
p = 0 # 全体を分割するのでp=0
partition_idx = partition(A, p, r)
for i in range(n):
    if i == partition_idx:
        print(f"[{A[i]}]",end="")
    else:
        print(f"{A[i]}",end="")
        
    # 最後のインデックス以外なら空白を入れる
    if i != n-1:
        print(" ",end="")
    
print() # 最後は改行

3. ALDS1_6_C: Quick Sort

# ALDS1_6_C
# A[p:r] を A[r]を基準に分割する
def partition(A, p, r):
    x = A[r][1] # カード用に[1]を付けた
    i = p-1
    for j in range(p,r):
        if A[j][1] <= x: # カード用に[1]を付けた
            i = i+1
            # A[i] と A[j] を交換
            tmp = A[i]
            A[i] = A[j]
            A[j] = tmp
            
    # A[i+1] と A[r] を交換
    tmp = A[i+1]
    A[i+1] = A[r]
    A[r] = tmp
    return i+1

def quickSort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quickSort(A, p, q-1)
        quickSort(A, q+1, r)
        
n = int(input())
card_list = []
for _ in range(n):
    card = input().split(" ")
    card = [card[0],int(card[1])]
    card_list.append(card)
    
# 順序を記録しておく
order_dict = {}
for card in card_list:
    if card[1] in order_dict.keys():
        order_dict[card[1]].append(card)
    else:
        order_dict[card[1]] = [card]

quickSort(card_list, 0, n-1)

# 並べ替え後の順序を調べる
order_dict2 = {}
for card in card_list:
    if card[1] in order_dict2.keys():
        order_dict2[card[1]].append(card)
    else:
        order_dict2[card[1]] = [card]

# 並べ替えの前後で順序が同じならStable
if order_dict == order_dict2:
    print("Stable")
else:
    print("Not stable")

for card in  card_list:
    print(*card)

4. ALDS1_6_D: Minimum Cost Sort

試したこと1

• 正しい位置にある物を動かすことは完全に無駄
• 重さwの物を移動するのにかかる最小のコストはw+min(W), Wは正しい位置にない物の重さの集合
• w_min と w_minの位置に収まるべきものを入れ替え続ける 1個または2個揃う
• 2個揃った場合はw_minを更新し全部揃うまで同じことを続ける

試したこと2

• 各要素の入れ替えで2個揃うような場合以外は上の主張は正しい
• 2個揃う場合のみが問題なので，2個揃ってしまう場合は，1個しか揃わないような次の最小の要素と入れ替える

試したこと3

• 2個揃う場合が問題ならば，1個ずつしか揃わないようなグループに最小要素を追加したときのコストとしなかったときのコストを比較して部分問題を解いていく
• しかし，本当にこれで最小コストになるのかはわからない...(グループ同士を結合したほうがコストが少なくなる場合は部分問題にならない)

# ALDS1_6_D
n = int(input())
W = list(map(int,input().split(" ")))
W_sorted = sorted(W)

cost = 0
rest_W = W[:]

group_list = []

def group_cost(group,min_w):
    # 追加しない場合 (最小値が移動する回数) * (最小値) + (他の要素の1回ずつの移動)
    cost1 = (len(group)-1) * min(group) + sum(group) - min(group)
    # 追加する場合 (最小値が移動する回数) * (最小値) + (グループの最小を最初に交換するコスト) + (他の要素の1回ずつの移動)
    cost2 = min_w * (len(group)+1) + min(group) + sum(group)
    return min(cost1,cost2)

# 試行錯誤の名残で最小値を探しているだけ
def swap_min(group=[]):
    min_w = min(rest_W) # 最小の物を探す
    min_pos = rest_W.index(min_w)
    w_pos = W.index(W_sorted[min_pos]) # その位置に収まるべき物を探す

    # 入れ替えを行う
    tmp = W[w_pos]
    W[w_pos] = min_w
    W[min_pos] = tmp
    
    rest_W[min_pos] = float("inf") # min_posには必ず正しいものが入る
    if min_pos == w_pos:
        group.append(tmp)
        group_list.append(group)
        group = []
        return group
    
    # 入れ替えの結果 w_posも正しくなった場合
    if W_sorted[w_pos] == W[w_pos]:
        rest_W[w_pos] = float("inf")
        group.append(min_w)
        group.append(tmp)
        group_list.append(group)
        group = []
        return group
    else:
        rest_W[w_pos] = min_w
        group.append(tmp)
        return group
    
# グループ分けをする(巡回置換の積に書き直す)
group = []
while len(set(rest_W)) > 1:
    group = swap_min(group) 
    
cost = 0
min_w = min(W)
for group in group_list:
    # print(group,group_cost(group,min_w))
    cost += group_cost(group,min_w)
    
print(cost)