ALDS1_5の解答例(Python)

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

1. ALDS1_5_A: Exhaustive Search

# ALDS1_5_A
from bisect import bisect_left
from itertools import combinations

dummy = input()
A = list(map(int,input().split(" ")))
A.sort()
dummy = input()
B = list(map(int,input().split(" ")))

for b in B:
    idx = bisect_left(A,b) # bより小さい要素だけをスライスする
    sub_A = A[:idx+1]
    flag = False
    # 全部足してもbより少ないならやる必要はない
    if sum(sub_A) >= b:
        # すべての組み合わせに対して和を調べる(総当たり)
        for i in range(len(sub_A)+1):
            combs = combinations(sub_A,i) 
            for comb in combs:
                if b == sum(comb):
                    flag = True
                    break

            if flag:
                break

    if flag:
        print("yes")
    else:
        print("no")

2. ALDS1_5_B: Merge Sort

# ALDS1_5_B
# 結合をするときに並べ替えが起こる
def merge(A, left, mid, right):
    global cnt
    L = A[left:mid]
    R = A[mid:right]
    
    # どのように並べ替えが起きているのか見たい場合
    # print(*A)
    # print(L,R)
    
    # インデックスエラーを防ぐためにinfを末尾に追加
    L.append(float("inf"))
    R.append(float("inf"))
    
    a_idx = left
    r_idx = 0
    l_idx = 0
    while a_idx in range(left,right): 
        if L[l_idx] <= R[r_idx]:
            A[a_idx] = L[l_idx]
            l_idx += 1
        else:
            A[a_idx] = R[r_idx]
            r_idx += 1
            
        a_idx += 1
        cnt += 1

# left rightが1つになるまで分割した後に結合していく
def mergeSort(A, left, right):
    if left+1 < right:
        mid = (left + right)//2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)
        
cnt = 0
dummy = input()
A = list(map(int,input().split(" ")))
mergeSort(A, 0, len(A))
print(*A)
print(cnt)

3. ALDS1_5_C: Koch Curve

# ALDS1_5_C 
import math

def koch_curve(p_list):
    a = p_list[0][0]
    b = p_list[0][1]
    result_list = [(0,0)]
    deg60 = math.pi/3 # ラジアンで60度を用意しておく
    for i in range(len(p_list)-1):
        p1,p2 = p_list[i],p_list[i+1]
        # s, t は内分で求める
        s = ((2*p1[0] + p2[0])/3, (2*p1[1]+p2[1])/3)
        t = ((p1[0] + 2*p2[0])/3, (p1[1]+2*p2[1])/3)
        # s,t を60度回転したらuの座標が出る
        u_x = (t[0]-s[0])*math.cos(deg60) - (t[1]-s[1])*math.sin(deg60) + s[0]
        u_y = (t[0]-s[0])*math.sin(deg60) + (t[1]-s[1])*math.cos(deg60) + s[1]
        u = (u_x,u_y)
        
        # 既に追加されているp1以外を追加
        result_list.extend([s,u,t,p2])
        
    return result_list

n = int(input())
p_list = [(0,0),(100,0)] # n=0のときの座標
for _ in range(n):
    p_list = koch_curve(p_list)

for p in p_list:
    print(*p)

4. ALDS1_5_D: The Number of Inversions

# ALDS1_5_D (TLE)
from bisect import bisect_left
n = int(input())
A = list(map(int,input().split(" ")))
B = []

ans = 0
for a in A:
    idx = bisect_left(B,a) # 二分探索で挿入すべき場所を探す : O(log(n))
    ans += len(B)-idx # a_i > a_j かつ i < jの組の数 
    B.insert(idx,a) # Bに挿入 : 0.5*n*(n+1) → O(n**2)
    
print(ans)

# ALDS1_5_D 
# コード全体の計算量はソートのn*log(n)程度
from bisect import bisect_left

# どのBに追加するかを探す
def find_B(a):
    for key in B_dict:
        if a <= B_dict[key]:
            return key

n = int(input())
A = list(map(int,input().split(" ")))
A_sort = sorted(A) # ソートの計算量 : n*log(n) 

B = [[] for _ in range(100)]
B_dict = {} # B[i-1] に入る最大の要素を記録する辞書
for i in range(1,101):
    if i*2000 < len(A):
        B_dict[i-1] = A_sort[i*2000]
    else:
        B_dict[i-1] = A_sort[-1]
        break

length = [0 for i in range(100)] # length[i] = len(B[0]) + len(B[1]) + ... + len(B[i])

ans = 0
for a in A:
    idx1 = find_B(a)
    idx = bisect_left(B[idx1],a) # 二分探索 : log(2000) (B[i]の長さは最悪でも2000なので) 
    ans += length[idx1]+len(B[idx1])-idx
    B[idx1].insert(idx,a) # 挿入 : O(2000) (最悪の場合)
    for i in range(idx1):
        length[i] += 1
    
print(ans)