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

ALDS1_4の解答例(Python)

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

1. ALDS1_4_A: Linear Search

線形探索に関する問題です． Tの要素がSに含まれるかをループで回して順番に判定しています．


# ALDS1_4_A

# リストの受け取り
dummy = input()
S = list(map(int,input().split(" ")))
dummy = input()
T = list(map(int,input().split(" ")))

# Tの要素がSに含まれているかを判定
cnt = 0
for t in T:
    cnt += (t in S)
    
print(cnt)

2. ALDS1_4_B: Binary Search

二分探索を使ってAと同じことをやります． bisect_leftを使っているので二分探索に関して自分では書いていません． ITP2_6の解答例で二分探索を自力で書いていますので，二分探索についてはこちらをご覧ください．


# ALDS1_4_B
from bisect import bisect_left

# リストの受け取り 
dummy = input()
S = list(map(int,input().split(" ")))
dummy = input()
T = list(map(int,input().split(" ")))

cnt = 0
for t in T:
    # bisect_leftで一致する可能性のある位置を二分探索する
    idx = bisect_left(S,t) 
    if idx < len(S): # len(S):末尾が返ってくることがある
        if t == S[idx]:
            cnt += 1
        
print(cnt)

3. ALDS1_4_C: Dictionary

命令文に従って辞書の操作を行う問題です．キーを使わないのでsetの方が無駄がないですが，タイトルにつられてdictを使って書いています．


# ALDS1_4_C
str_dict = {}
ite = int(input())
for _ in range(ite):
    command, s = input().split(" ")
    if command == "insert":
        str_dict[s] = 0
    elif command == "find":
        if s in str_dict.keys():
            print("yes")
        else:
            print("no")

4. ALDS1_4_D: Allocation

指定されたトラックの台数と荷物に対して最大積載量を超えないように荷物を積み込めるような最大積載量の最小値を探す問題です．二分探索を使って最大積載量を求めることでループの回数をlog(n*weight)程度まで抑えます．(最悪でも20回程度になります)


# ALDS1_4_D 二分探索
import math
n,k = map(int,input().split(" "))

# 重さのリストを作る
weight_list = []
for _ in range(n):
    weight_list.append(int(input()))
    
# 二分探索用の変数
right = sum(weight_list) # 全部を1台で積める
left = max(max(weight_list),math.ceil(sum(weight_list)/k)) # 最低でも最大重量分は積めないといけない
capacity = (right+left)//2

# クリアできた積載量を保存しておく
clear_capacity = float("inf")

while True:
    current_capacity = capacity # 残りの容量
    track_num = 1
    for weight in weight_list:
        if current_capacity < weight:
            current_capacity = capacity - weight
            track_num += 1 # 使ったトラックの台数を増やす
        else:
            current_capacity -= weight
            
        # トラックの台数がkを超えたらその時点で終了
        if k < track_num:
            break
            
    # 余裕があればrightを小さくしてcapacityを更新
    if k >= track_num:
        right = (left+right)//2 - 1
        clear_capacity = min(clear_capacity,capacity) # クリアできた容量を記憶しておく
    # 足りなければleftを増やしてcapacityを更新
    else:
        left = (left+right)//2 + 1
        
    if left <= right:
        capacity = (left+right)//2
    else:
        break
    
print(clear_capacity)

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