トップページ -> AOJの解答例 -> ALDS1_1の解答例

ALDS1_1の解答例(Python)

挿入ソート，最大公約数，素数判定，最大利益を求める問題です．計算量を考慮しないと，時間制限に引っかかるかもしれません．

1. ALDS1_1_A: Insertion Sort

挿入ソートに関する問題です．問題文に載っている疑似コードの通りに書きました．

挿入ソートについて

トランプゲーム(例えば大富豪)で手札を右に行くにつれて数字が大きくなるように並べることを考えます．配られた時点での手札が 8,4,6,10,9,12,7 だったとします．
挿入ソートでは，小さいNから順にN番目のカードがN-1番目までのどこに挿入できるかを考えます．
N=1の場合 4が[8]のどこに挿入できるかを考えます．[4,8]となります．
N=2の場合 6が[4,8]のどこに挿入できるかを考えます．[4,6,8]となります．
N=3の場合 10が[4,6,8]のどこに挿入できるかを考えます．[4,6,8,10]となります．
以下同様


# ALDS1_1_A
# 問題文にあるものをそのまま実装する
def insertion_sort(A,N):
    for i in range(len(A)):
        v = A[i]
        j = i-1
        while j>=0 and A[j]>v:
            A[j+1] = A[j]
            j -= 1
        
        A[j+1] = v
        print(*A)
        
N = int(input())
A = list(map(int,input().split(" ")))
insertion_sort(A,N)

2. ALDS1_1_B: Greatest Common Divisor

最大公約数を求める問題です．ヒントに書いてあるように互除法を使って書きました．
【外部サイト】ユークリッドの互除法まとめ（証明・最大公約数・不定方程式


# ALDS1_1_B
# 互除法を使う

def solve_gcd(x,y):
    x,y = max(x,y),min(x,y)
    if x%y == 0:
        return y
    return solve_gcd(x%y,y)
    
x,y = list(map(int,input().split(" ")))
gcd = solve_gcd(x,y)
print(gcd)

3. ALDS1_1_C: Prime Numbers

素数を判定する問題です． nが√n以上の約数を持つことがないことを利用してループの範囲を工夫しています．


# ALDS1_1_C
# 単純に 2から√xまでループを回して割ってみる
def is_prime(x):
    if x == 1:
        return False
    elif x == 2:
        return True
    # nが√n以上の約数を持つことはないのでint(x**0.5)+1までで十分
    else:
        for i in range(2,int(x**0.5)+1):
            if x%i == 0:
                return False
            
        return True
    
ite = int(input())
cnt = 0
for _ in range(ite):
    n = int(input())
    cnt += is_prime(n)
    
print(cnt)

4. ALDS1_1_D: Maximum Profit

為替取引での最大利益を求める問題です．現時点で売った場合の利益(value-min_value)を調べた後に，現時点までの最安値(min_value)を更新しています．


# ALDS1_1_D

m = int(input())

# 範囲外の数値で初期化しておく float('inf')でもいい
min_value = 10**10
max_profit = -10**10

for _ in range(m):
    value = int(input())
    # 現在の価格 - 最安値 が今売ったときの利益
    if max_profit < value - min_value:
        max_profit = value - min_value
        
    # 最安値を更新する
    if min_value > value:
        min_value = value
        
print(max_profit)

<- 前へ戻る【目次に戻る】次へ進む ->