ALDS1_15の解答例(Python)

カテゴリーはよく分かりませんが，お釣りの支払い，有利ナップサック問題，活動選択問題，ハフマン符号に関する問題です． アルゴリズムについて詳しく知りたい方は参考文献などをご覧ください．

1. ALDS1_15_A: Change Making

# ALDS1_15_A
n = int(input())

coin = 0
coin_list = [25,10,5,1] # コインの種類
# 大きい方から支払っていけばよい
for c in coin_list:
    num = n//c
    coin += num
    n = n - num*c
    if n == 0:
        break

print(coin)

2. ALDS1_15_B: Fractional Knapsack Problem

# ALDS1_15_B

# 重さ1あたりの価値が高いものを貪欲に取る
N,W = list(map(int,input().split(" ")))

# 追加できる量と重さ1あたりの価値を記録
v_list = []
for _ in range(N):
    v,w = list(map(int,input().split(" ")))
    v_list.append([v/w,w])
    
ans = 0
# 価値の高いものから取る
v_list.sort(reverse=True)
for v in v_list:
    # 容量をオーバーしないなら全て追加
    if v[1] <= W:
        ans += v[0]*v[1]
        W -= v[1]
    # 容量をオーバーするなら残り分追加
    else:
        ans += W*v[0]
        W = 0
        
    if W <= 0:
        break
        
print(ans)

3. ALDS1_15_C: Activity Selection Problem

# ALDS1_15_C
n = int(input())

end = 0 # 最後に参加した活動の終了時刻を記録
activity_list = []
for _ in range(n):
    s,t = map(int,input().split(" "))
    # 終了時間のほうが重要なのでend startに直しておく
    activity_list.append([t,s])
    
# n log(n) n = 10**5
activity_list.sort() # 終了時刻の早い順に並び替え

cnt = 0
for activity in activity_list:
    # 参加予定の活動の終了時間より他の活動の開始時間が遅い(参加可能)
    if end < activity[1]:
        end = activity[0]
        cnt += 1
        
print(cnt)

4. ALDS1_15_D: Huffman Coding

# ALDS1_15_D
import heapq
from collections import deque

class Node:
    def __init__(self,count,key=None):
        self.count = count # 出現回数
        self.key = key # 文字の種類(文字を表すノードでなければNone)
        self.parent = None
        self.right = None
        self.left = None
        
    # 優先度付きキューを使うためにcountを基準に大小関係を定義した
    def __eq__(self, other):
        # イコールのみ not Noneを判定しないのでNode同士以外の比較もサポートする
        if not isinstance(other, Node):
            return False
        return self.count == other.count    

    def __lt__(self, other):
        if not isinstance(other, Node):
            return NotImplemented
        return self.count < other.count

    def __ne__(self, other):
        return not self.__eq__(other)

    def __le__(self, other):
        return self.__lt__(other) or self.__eq__(other)

    def __gt__(self, other):
        return not self.__le__(other)

    def __ge__(self, other):
        return not self.__lt__(other)

S = input()

# 文字が一種類の場合は全部0で構わない
if len(set(S)) == 1:
    print(len(S))
else:
    # 文字の種類別に出現回数を記録
    count_dict = {}
    for s in S:
        if s not in count_dict.keys():
            count_dict[s] = 0
        count_dict[s] += 1

    # 親を持たないノードのリスト
    no_parent_nodes = []
    for key in count_dict.keys():
        node = Node(count_dict[key],key)
        no_parent_nodes.append(node)

    heapq.heapify(no_parent_nodes) # countの少ない順に処理を施したいので優先度付きキューにする

    tree = []
    new_node = None
    # 親を持たないノードが1つ(根のみ)になるまで繰り返す
    while len(no_parent_nodes)!=1:
        # 出現回数の少ないノードを2つ取り出す
        node1 = heapq.heappop(no_parent_nodes)
        node2 = heapq.heappop(no_parent_nodes)

        # 出現回数の合計のノードを作る
        new_node = Node(node1.count+node2.count)
        new_node.left = node1 # 小さいほうを左の子にする
        new_node.right = node2 # 大きいほうを右の子にする
        heapq.heappush(no_parent_nodes,new_node)

        # node1 node2の親を設定して木に追加する
        node1.parent = new_node
        node2.parent = new_node
        tree.append(node1)
        tree.append(node2)

    if new_node:
        tree.append(new_node)

    # 幅優先探索で符号を割り当てる(全ての要素に辿り着ければなんでもいい)
    node_list = deque([[tree[-1],""]])
    sign_dict = {}
    while node_list:
        node,sign_bit = node_list.popleft()
        # 文字の種類のノードではない場合
        if node.key != None:
            sign_dict[node.key] = sign_bit

        # 左側 右側の子があれば0,1を足してnode_listに追加
        if node.left!=None:
            node_list.append([node.left,sign_bit+"0"])
        if node.right!=None:
            node_list.append([node.right,sign_bit+"1"])

    length = 0
    for key in sign_dict.keys():
        length += count_dict[key] * len(sign_dict[key])
    print(length)