def greedy_template(problem_input):
    """貪欲法の一般的なテンプレート"""
    # Step 1: 入力を貪欲基準でソート
    candidates = sort_by_greedy_criterion(problem_input)
 
    solution = []
 
    # Step 2: 各候補について判定
    for candidate in candidates:
        if is_feasible(solution, candidate):
            # Step 3: 制約を満たすなら解に追加
            solution.append(candidate)
 
    return solution

def activity_selection(activities: list) -> list:
    """活動選択問題 - O(n log n)
    activities: [(start, end), ...]
    """
    # 終了時間でソート
    sorted_acts = sorted(activities, key=lambda x: x[1])
    selected = [sorted_acts[0]]
    last_end = sorted_acts[0][1]
 
    for start, end in sorted_acts[1:]:
        if start >= last_end:  # 前の活動と重ならない
            selected.append((start, end))
            last_end = end
 
    return selected
 
activities = [(1,4), (3,5), (0,6), (5,7), (3,9), (5,9),
              (6,8), (8,11), (8,12), (2,14), (12,16)]
result = activity_selection(activities)
print(f"選択された活動: {result}")
# [(1, 4), (5, 7), (8, 11), (12, 16)]
print(f"活動数: {len(result)}")  # 4

import bisect
 
def weighted_activity_selection(activities: list) -> int:
    """重み付き活動選択問題 - O(n log n)
    activities: [(start, end, weight), ...]
    貪欲では解けないため DP を使う
    """
    # 終了時間でソート
    activities.sort(key=lambda x: x[1])
    n = len(activities)
 
    # 各活動 i に対して、i と重ならない直前の活動を二分探索で求める
    ends = [a[1] for a in activities]
 
    def latest_non_conflict(i):
        target = activities[i][0]
        idx = bisect.bisect_right(ends, target) - 1
        return idx if idx < i else idx
 
    # DP
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        # 活動 i-1 を含まない
        dp[i] = dp[i - 1]
        # 活動 i-1 を含む
        j = latest_non_conflict(i - 1)
        dp[i] = max(dp[i], dp[j + 1] + activities[i - 1][2])
 
    return dp[n]
 
activities_w = [(1, 4, 5), (3, 5, 6), (0, 6, 8), (5, 7, 4), (6, 9, 2)]
print(weighted_activity_selection(activities_w))  # 13 (活動(0,6,8) + (6,9,2) ?)

import heapq
from collections import Counter
 
class HuffmanNode:
    def __init__(self, char=None, freq=0, left=None, right=None):
        self.char = char
        self.freq = freq
        self.left = left
        self.right = right
 
    def __lt__(self, other):
        return self.freq < other.freq
 
def build_huffman_tree(freq: dict) -> HuffmanNode:
    """ハフマン木を構築 - O(n log n)"""
    heap = [HuffmanNode(char=c, freq=f) for c, f in freq.items()]
    heapq.heapify(heap)
 
    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        merged = HuffmanNode(freq=left.freq + right.freq,
                             left=left, right=right)
        heapq.heappush(heap, merged)
 
    return heap[0]
 
def build_codes(root: HuffmanNode, prefix="", codes=None) -> dict:
    """ハフマン符号を生成"""
    if codes is None:
        codes = {}
 
    if root.char is not None:
        codes[root.char] = prefix or "0"
        return codes
 
    if root.left:
        build_codes(root.left, prefix + "0", codes)
    if root.right:
        build_codes(root.right, prefix + "1", codes)
 
    return codes
 
def huffman_encode(text: str) -> tuple:
    """ハフマン符号化"""
    freq = Counter(text)
    tree = build_huffman_tree(freq)
    codes = build_codes(tree)
    encoded = ''.join(codes[c] for c in text)
    return encoded, codes, tree
 
def huffman_decode(encoded: str, tree: HuffmanNode) -> str:
    """ハフマン復号"""
    result = []
    node = tree
    for bit in encoded:
        if bit == '0':
            node = node.left
        else:
            node = node.right
        if node.char is not None:
            result.append(node.char)
            node = tree
    return ''.join(result)
 
# 使用例
text = "aaaaabbbccddddeefffff"
encoded, codes, tree = huffman_encode(text)
print("符号表:", codes)
print(f"元のサイズ: {len(text) * 8} ビット")
print(f"圧縮後: {len(encoded)} ビット")
print(f"圧縮率: {len(encoded) / (len(text) * 8):.1%}")
 
# 復号して検証
decoded = huffman_decode(encoded, tree)
print(f"復号結果一致: {decoded == text}")  # True

# 実務では「静的ハフマン」よりも「適応型ハフマン」が使われることが多い
#
# 静的ハフマン:
#   - 全文を2パスで処理（1パス目で頻度計算、2パス目で符号化）
#   - 符号表をデータと一緒に保存する必要がある
#
# 適応型ハフマン (Adaptive Huffman):
#   - 1パスで処理（文字を読みながら木を更新）
#   - 符号表の伝送が不要
#   - gzip、DEFLATE アルゴリズム等で使用
#
# 実用的な圧縮ライブラリ:
#   - zlib: DEFLATE（LZ77 + ハフマン）
#   - brotli: LZ77 + ハフマン + コンテキストモデリング
#   - zstd: LZ77 + FSE（有限状態エントロピー）

class UnionFind:
    """Union-Find（Kruskal用）"""
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.size = [1] * n
 
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 経路圧縮
        return self.parent[x]
 
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        self.size[px] += self.size[py]
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        return True
 
    def connected(self, x, y):
        return self.find(x) == self.find(y)
 
def kruskal(n: int, edges: list) -> tuple:
    """Kruskal法 - O(E log E)
    edges: [(weight, u, v), ...]
    返り値: (MST辺リスト, 合計重み)
    """
    edges.sort()  # 重みでソート
    uf = UnionFind(n)
    mst = []
    total = 0
 
    for w, u, v in edges:
        if uf.union(u, v):
            mst.append((u, v, w))
            total += w
            if len(mst) == n - 1:
                break
 
    return mst, total
 
# 頂点: 0=A, 1=B, 2=C, 3=D, 4=E
edges = [(4,0,1), (8,0,2), (2,1,2), (6,1,3), (3,2,3), (7,2,4), (9,3,4)]
mst, total = kruskal(5, edges)
print(f"MST辺: {mst}")     # [(1, 2, 2), (2, 3, 3), (0, 1, 4), (2, 4, 7)]
print(f"合計重み: {total}")  # 16

import heapq
 
def prim(graph: dict, start: int = 0) -> tuple:
    """Prim法 - O((V + E) log V)
    graph: {u: [(v, weight), ...]}
    返り値: (MST辺リスト, 合計重み)
    """
    mst = []
    total = 0
    visited = {start}
    # (weight, from, to) のヒープ
    edges = [(w, start, v) for v, w in graph[start]]
    heapq.heapify(edges)
 
    while edges and len(mst) < len(graph) - 1:
        w, u, v = heapq.heappop(edges)
        if v in visited:
            continue
        visited.add(v)
        mst.append((u, v, w))
        total += w
 
        for next_v, next_w in graph[v]:
            if next_v not in visited:
                heapq.heappush(edges, (next_w, v, next_v))
 
    return mst, total
 
graph_prim = {
    0: [(1, 4), (2, 8)],
    1: [(0, 4), (2, 2), (3, 6)],
    2: [(0, 8), (1, 2), (3, 3), (4, 7)],
    3: [(1, 6), (2, 3), (4, 9)],
    4: [(2, 7), (3, 9)],
}
mst, total = prim(graph_prim)
print(f"MST辺: {mst}")     # Kruskal と同じ結果
print(f"合計重み: {total}")  # 16

def boruvka(n: int, edges: list) -> tuple:
    """Boruvka法 - O(E log V)
    edges: [(u, v, weight), ...]
    並列処理に適したMSTアルゴリズム
    """
    uf = UnionFind(n)
    mst = []
    total = 0
    num_components = n
 
    while num_components > 1:
        # 各連結成分の最小辺を記録
        cheapest = [None] * n  # cheapest[comp] = (weight, u, v)
 
        for u, v, w in edges:
            comp_u = uf.find(u)
            comp_v = uf.find(v)
 
            if comp_u == comp_v:
                continue  # 同じ連結成分
 
            if cheapest[comp_u] is None or w < cheapest[comp_u][0]:
                cheapest[comp_u] = (w, u, v)
            if cheapest[comp_v] is None or w < cheapest[comp_v][0]:
                cheapest[comp_v] = (w, u, v)
 
        # 各連結成分の最小辺を追加
        for comp in range(n):
            if cheapest[comp] is not None:
                w, u, v = cheapest[comp]
                if uf.find(u) != uf.find(v):
                    uf.union(u, v)
                    mst.append((u, v, w))
                    total += w
                    num_components -= 1
 
    return mst, total
 
# 使用例
edges_b = [(0,1,4), (0,2,8), (1,2,2), (1,3,6), (2,3,3), (2,4,7), (3,4,9)]
mst_b, total_b = boruvka(5, edges_b)
print(f"Boruvka MST: {mst_b}")
print(f"合計重み: {total_b}")  # 16

def fractional_knapsack(items: list, capacity: float) -> float:
    """分数ナップサック - O(n log n)
    items: [(weight, value), ...]
    """
    # 単位重さあたりの価値でソート（降順）
    items_sorted = sorted(items, key=lambda x: x[1]/x[0], reverse=True)
 
    total_value = 0.0
    remaining = capacity
 
    for weight, value in items_sorted:
        if remaining >= weight:
            total_value += value
            remaining -= weight
        else:
            total_value += value * (remaining / weight)
            break
 
    return total_value
 
items = [(10, 60), (20, 100), (30, 120)]
print(fractional_knapsack(items, 50))  # 240.0

def interval_scheduling(intervals: list) -> int:
    """重ならない区間の最大数 - O(n log n)"""
    intervals.sort(key=lambda x: x[1])  # 終了時間でソート
    count = 0
    last_end = float('-inf')
 
    for start, end in intervals:
        if start >= last_end:
            count += 1
            last_end = end
 
    return count
 
intervals = [(1,3), (2,5), (4,7), (1,8), (5,9), (8,10)]
print(interval_scheduling(intervals))  # 3: (1,3), (4,7), (8,10)

def min_interval_cover(intervals: list, target_start: int, target_end: int) -> list:
    """[target_start, target_end] を最小数の区間でカバー - O(n log n)"""
    intervals.sort()
    result = []
    i = 0
    n = len(intervals)
    current = target_start
 
    while current < target_end and i < n:
        # current 以前に始まり、最も遠くまで伸びる区間を選ぶ
        best_end = current
        while i < n and intervals[i][0] <= current:
            best_end = max(best_end, intervals[i][1])
            i += 1
 
        if best_end == current:
            return []  # カバーできない
 
        result.append(best_end)
        current = best_end
 
    return result if current >= target_end else []
 
intervals = [(0, 3), (1, 5), (2, 7), (4, 9), (6, 10)]
print(min_interval_cover(intervals, 0, 10))  # [3, 7, 10]

def job_scheduling_with_deadlines(jobs: list) -> tuple:
    """デッドライン付きジョブスケジューリング - O(n² log n)
    jobs: [(deadline, profit), ...]
    各ジョブは1単位時間で完了。デッドラインまでに完了すれば利益を得る。
    """
    # 利益の降順でソート
    jobs_sorted = sorted(enumerate(jobs), key=lambda x: x[1][1], reverse=True)
    max_deadline = max(d for d, _ in jobs)
 
    # スロット管理（1-indexed）
    slots = [False] * (max_deadline + 1)
    result = []
    total_profit = 0
 
    for idx, (deadline, profit) in jobs_sorted:
        # デッドライン以前で最も遅い空きスロットを探す
        for t in range(min(deadline, max_deadline), 0, -1):
            if not slots[t]:
                slots[t] = True
                result.append((idx, t, profit))
                total_profit += profit
                break
 
    return total_profit, result
 
jobs = [(2, 100), (1, 19), (2, 27), (1, 25), (3, 15)]
profit, schedule = job_scheduling_with_deadlines(jobs)
print(f"最大利益: {profit}")    # 142
print(f"スケジュール: {schedule}")

def run_length_encode(s: str) -> str:
    """ランレングス符号化 — 貪欲法の一種"""
    if not s:
        return ""
 
    result = []
    count = 1
 
    for i in range(1, len(s)):
        if s[i] == s[i - 1]:
            count += 1
        else:
            result.append(f"{s[i-1]}{count}")
            count = 1
 
    result.append(f"{s[-1]}{count}")
    return ''.join(result)
 
def run_length_decode(encoded: str) -> str:
    """ランレングス復号"""
    result = []
    i = 0
    while i < len(encoded):
        char = encoded[i]
        i += 1
        num = []
        while i < len(encoded) and encoded[i].isdigit():
            num.append(encoded[i])
            i += 1
        result.append(char * int(''.join(num)))
    return ''.join(result)
 
original = "AAABBBCCDDDDEEFFFFF"
encoded = run_length_encode(original)
print(f"符号化: {encoded}")      # A3B3C2D4E2F5
print(f"復号化: {run_length_decode(encoded)}")  # AAABBBCCDDDDEEFFFFF

# Dijkstra法は貪欲法の一例として理解できる:
#
# 貪欲選択: 「未確定頂点の中で距離が最小の頂点を確定する」
#
# 貪欲選択性質の証明:
#   - 未確定頂点 u の距離 d[u] が最小
#   - 別の経路 s → ... → w → ... → u が d[u] より短いと仮定
#   - しかし w は未確定なので d[w] >= d[u]
#   - 辺の重みは非負なので w 経由の経路は d[w] 以上 >= d[u]
#   - 矛盾 → d[u] は最短
#
# この証明が成り立つ条件: 全辺の重みが非負
# 負辺があると成り立たない → Bellman-Ford（DPベース）が必要

def min_gas_stops(stations: list, tank_capacity: int, total_distance: int) -> list:
    """ガソリンスタンド問題 - O(n)
    stations: ガソリンスタンドの位置（距離）のリスト（ソート済み）
    tank_capacity: 満タンで走れる距離
    total_distance: 目的地までの総距離
 
    貪欲戦略: 現在の燃料で到達可能な最も遠いスタンドで給油する
    """
    stops = []
    current_fuel = tank_capacity
    current_pos = 0
 
    # 目的地もリストに加える
    all_points = stations + [total_distance]
 
    for point in all_points:
        distance = point - current_pos
 
        if distance > tank_capacity:
            return []  # 到達不可能
 
        if current_fuel < distance:
            # 燃料不足 → 直前のスタンドで給油が必要だった
            # このアルゴリズムでは「行けるだけ行って給油」戦略
            stops.append(current_pos)
            current_fuel = tank_capacity
 
        current_fuel -= distance
        current_pos = point
 
    return stops
 
 
def min_gas_stops_greedy(stations: list, tank_capacity: int, total_distance: int) -> list:
    """改良版: 行けるだけ行ってから給油する貪欲法 - O(n)"""
    if not stations:
        return [] if tank_capacity >= total_distance else [-1]
 
    stops = []
    current_fuel = tank_capacity
    prev_pos = 0
 
    for i, station_pos in enumerate(stations):
        dist = station_pos - prev_pos
 
        if dist > current_fuel:
            # ここまで来られない → 直前のスタンドで給油すべきだった
            # 直前のスタンドがないなら到達不可能
            if not stops and prev_pos == 0:
                return [-1]  # 到達不可能
            current_fuel = tank_capacity
            dist = station_pos - prev_pos
            if dist > current_fuel:
                return [-1]
 
        current_fuel -= dist
        prev_pos = station_pos
 
        # 次のポイントまで行けるか確認
        next_point = stations[i + 1] if i + 1 < len(stations) else total_distance
        if current_fuel < next_point - station_pos:
            stops.append(station_pos)
            current_fuel = tank_capacity
 
    # 最後の区間
    if current_fuel < total_distance - prev_pos:
        return [-1]
 
    return stops
 
# 使用例
stations = [100, 200, 375, 550, 750]
tank = 400
distance = 900
result = min_gas_stops_greedy(stations, tank, distance)
print(f"給油地点: {result}")  # 到達可能な最小停車

def verify_matroid_greedy(elements: list, weights: dict,
                          is_independent) -> list:
    """マトロイド上の重み最大独立集合を貪欲法で求める
    elements: 元の集合
    weights: 各要素の重み
    is_independent: 独立性を判定する関数
    """
    # 重みの降順にソート
    sorted_elements = sorted(elements, key=lambda x: weights[x], reverse=True)
 
    solution = []
    for elem in sorted_elements:
        candidate = solution + [elem]
        if is_independent(candidate):
            solution.append(elem)
 
    return solution
 
# 一様マトロイドの例: 上位k個の重み最大要素を選ぶ
elements = ['a', 'b', 'c', 'd', 'e']
weights = {'a': 10, 'b': 30, 'c': 20, 'd': 5, 'e': 25}
k = 3
 
def uniform_independent(subset):
    return len(subset) <= k
 
result = verify_matroid_greedy(elements, weights, uniform_independent)
print(f"選択: {result}")  # ['b', 'e', 'c'] (重み: 30, 25, 20)
print(f"合計重み: {sum(weights[x] for x in result)}")  # 75

def greedy_facility_placement(cities: list, k: int) -> list:
    """k 個の施設を貪欲に配置（最大距離の最小化）
    これは近似アルゴリズム（最適解の2倍以内を保証）
    """
    n = len(cities)
    if k >= n:
        return list(range(n))
 
    # 最初の施設: 任意（ここでは都市0）
    facilities = [0]
    min_dist = [float('inf')] * n
 
    for _ in range(k - 1):
        # 各都市の最寄り施設までの距離を更新
        last = facilities[-1]
        for j in range(n):
            d = abs(cities[j][0] - cities[last][0]) + abs(cities[j][1] - cities[last][1])
            min_dist[j] = min(min_dist[j], d)
 
        # 最寄り施設から最も遠い都市を次の施設に
        farthest = max(range(n), key=lambda j: min_dist[j] if j not in facilities else -1)
        facilities.append(farthest)
 
    return facilities

def minimize_lateness(tasks: list) -> tuple:
    """遅延の最大値を最小化するスケジューリング
    tasks: [(processing_time, deadline), ...]
    最適戦略: 締め切りが早い順に処理（EDF: Earliest Deadline First）
    """
    indexed = [(d, p, i) for i, (p, d) in enumerate(tasks)]
    indexed.sort()  # 締め切り順
 
    schedule = []
    current_time = 0
    max_lateness = 0
 
    for deadline, proc_time, idx in indexed:
        start = current_time
        finish = current_time + proc_time
        lateness = max(0, finish - deadline)
        max_lateness = max(max_lateness, lateness)
        schedule.append((idx, start, finish, lateness))
        current_time = finish
 
    return max_lateness, schedule
 
tasks = [(3, 6), (2, 8), (1, 9), (4, 9), (3, 14), (2, 15)]
max_late, sched = minimize_lateness(tasks)
print(f"最大遅延: {max_late}")
for idx, start, finish, late in sched:
    print(f"  タスク{idx}: {start}-{finish} (遅延: {late})")

def optimal_page_replacement(pages: list, cache_size: int) -> int:
    """Belady の最適ページ置換アルゴリズム（将来のアクセスを知っている前提）
    page fault の回数を返す
    """
    cache = set()
    faults = 0
 
    for i, page in enumerate(pages):
        if page in cache:
            continue
 
        faults += 1
 
        if len(cache) < cache_size:
            cache.add(page)
        else:
            # キャッシュ内で、次に使われるのが最も遅いページを追い出す
            farthest = -1
            victim = None
            for cached_page in cache:
                try:
                    next_use = pages[i+1:].index(cached_page)
                except ValueError:
                    next_use = float('inf')  # 二度と使われない
 
                if next_use > farthest:
                    farthest = next_use
                    victim = cached_page
 
            cache.remove(victim)
            cache.add(page)
 
    return faults
 
pages = [7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1]
print(f"Page faults (OPT): {optimal_page_replacement(pages, 3)}")   # 9
print(f"Page faults (OPT): {optimal_page_replacement(pages, 4)}")   # 6

def greedy_set_cover(universe: set, subsets: list) -> list:
    """集合被覆問題の貪欲近似 - O(|U| * |S|)
    NP困難問題だが、貪欲法で ln(|U|)+1 倍以内の近似解を得られる
    """
    uncovered = set(universe)
    selected = []
 
    while uncovered:
        # 未カバー要素を最も多くカバーする集合を選ぶ
        best = max(range(len(subsets)),
                   key=lambda i: len(subsets[i] & uncovered) if i not in selected else 0)
 
        if not (subsets[best] & uncovered):
            break  # これ以上カバーできない
 
        selected.append(best)
        uncovered -= subsets[best]
 
    return selected
 
universe = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
subsets = [
    {1, 2, 3, 8},      # S0
    {1, 2, 3, 4, 5},   # S1
    {4, 5, 7},          # S2
    {5, 6, 7},          # S3
    {6, 7, 8, 9, 10},  # S4
]
selected = greedy_set_cover(universe, subsets)
print(f"選択された集合: {selected}")  # [1, 4] or similar

def greedy_graph_coloring(graph: dict) -> dict:
    """貪欲法によるグラフ彩色 - O(V + E)
    graph: {node: [neighbors]}
    最適解は保証しないが、最大次数+1色以内で彩色可能（Brook の定理）
    """
    colors = {}
 
    for node in graph:
        # 隣接頂点が使っている色を収集
        used_colors = set()
        for neighbor in graph[node]:
            if neighbor in colors:
                used_colors.add(colors[neighbor])
 
        # 使われていない最小の色番号を割り当て
        color = 0
        while color in used_colors:
            color += 1
        colors[node] = color
 
    return colors
 
# 使用例: ペテルセングラフの一部
graph = {
    0: [1, 4, 5],
    1: [0, 2, 6],
    2: [1, 3, 7],
    3: [2, 4, 8],
    4: [3, 0, 9],
    5: [0, 7, 8],
    6: [1, 8, 9],
    7: [2, 5, 9],
    8: [3, 5, 6],
    9: [4, 6, 7],
}
coloring = greedy_graph_coloring(graph)
num_colors = len(set(coloring.values()))
print(f"彩色結果: {coloring}")
print(f"使用色数: {num_colors}")
 
# 彩色の妥当性を検証
valid = all(
    coloring[u] != coloring[v]
    for u in graph for v in graph[u]
)
print(f"彩色は有効: {valid}")  # True

import heapq
 
def optimal_merge_pattern(file_sizes: list) -> tuple:
    """最適マージパターン - O(n log n)
    各ステップで最も小さい2つのファイルをマージする（ハフマンと同じ戦略）
    返り値: (合計マージコスト, マージ順序)
    """
    heap = list(file_sizes)
    heapq.heapify(heap)
    total_cost = 0
    merge_order = []
 
    while len(heap) > 1:
        first = heapq.heappop(heap)
        second = heapq.heappop(heap)
        merged = first + second
        total_cost += merged
        merge_order.append((first, second, merged))
        heapq.heappush(heap, merged)
 
    return total_cost, merge_order
 
# 使用例
sizes = [20, 30, 10, 5, 30]
cost, order = optimal_merge_pattern(sizes)
print(f"最小マージコスト: {cost}")
for f1, f2, merged in order:
    print(f"  {f1} + {f2} = {merged}")
# 出力例:
# 5 + 10 = 15
# 15 + 20 = 35
# 30 + 30 = 60
# 35 + 60 = 95
# 合計コスト = 15 + 35 + 60 + 95 = 205

# BAD: 「直感的に正しそう」で貪欲法を適用
# コイン問題: 額面 = [1, 3, 4], 金額 = 6
# 貪欲（最大額面優先）: 4 + 1 + 1 = 3枚
# 最適解: 3 + 3 = 2枚  ← 貪欲は失敗!
 
def bad_coin_greedy(coins, amount):
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        count += amount // coin
        amount %= coin
    return count
 
print(bad_coin_greedy([1, 3, 4], 6))  # 3 (不正解、正解は2)
 
# GOOD: この問題にはDPを使う
def good_coin_dp(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for c in coins:
            if c <= i:
                dp[i] = min(dp[i], dp[i - c] + 1)
    return dp[amount]
 
print(good_coin_dp([1, 3, 4], 6))  # 2 (正解)

# BAD: 0/1ナップサックに単価順の貪欲を適用
# アイテム: (重さ=10, 価値=60), (重さ=20, 価値=100), (重さ=30, 価値=120)
# 容量: 50
# 貪欲（単価順）: 60 + 100 = 160
# 最適解: 100 + 120 = 220  ← 重さ20+30=50で入る
 
# GOOD: 0/1ナップサックにはDPを使う

# BAD: 活動選択で「開始時間」でソート → 最適でない
def bad_activity_selection(activities):
    activities.sort(key=lambda x: x[0])  # 開始時間でソート → 不正解
    ...
 
# GOOD: 「終了時間」でソート
def good_activity_selection(activities):
    activities.sort(key=lambda x: x[1])  # 終了時間でソート → 正解
    ...

# BAD: 集合被覆問題に貪欲を使い、「最適解が得られた」と主張
# → 貪欲は近似解であり、最適とは限らない
 
# GOOD: 近似比を明記する
# 「貪欲法による近似解。最適解の ln(n)+1 倍以内を保証」

# BAD: TSP に最近傍法（貪欲）を適用して「最適」と主張
def bad_tsp_nearest_neighbor(dist_matrix: list, start: int = 0) -> tuple:
    """最近傍法は貪欲ヒューリスティックであり、最適解を保証しない"""
    n = len(dist_matrix)
    visited = [False] * n
    visited[start] = True
    tour = [start]
    total = 0
    current = start
 
    for _ in range(n - 1):
        nearest = -1
        nearest_dist = float('inf')
        for j in range(n):
            if not visited[j] and dist_matrix[current][j] < nearest_dist:
                nearest = j
                nearest_dist = dist_matrix[current][j]
        visited[nearest] = True
        tour.append(nearest)
        total += nearest_dist
        current = nearest
 
    total += dist_matrix[current][start]
    tour.append(start)
    return total, tour
 
# 反例を示す距離行列
dist = [
    [0, 1, 15, 6],
    [1, 0, 7, 3],
    [15, 7, 0, 1],
    [6, 3, 1, 0],
]
greedy_cost, greedy_tour = bad_tsp_nearest_neighbor(dist, 0)
print(f"最近傍法: コスト={greedy_cost}, 経路={greedy_tour}")
# 最適経路は異なる場合がある
 
# GOOD: TSP には厳密解法（分枝限定法など）か、
# 2-opt 等の局所探索で改善する

# BAD: 負辺のあるグラフに Dijkstra（貪欲法）を適用
# → 負辺があると貪欲選択性質が崩壊する
#
# 例:  A --1--> B --(-3)--> C
#      A --2--> C
#
# Dijkstra: A→B(1), A→C(2) → Cの距離=2
# 正解: A→B→C = 1+(-3) = -2
#
# GOOD: 負辺がある場合は Bellman-Ford を使う
 
def bellman_ford(n: int, edges: list, source: int) -> list:
    """負辺を含むグラフの最短経路 - O(VE)"""
    dist = [float('inf')] * n
    dist[source] = 0
 
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
 
    # 負閉路の検出
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            raise ValueError("負閉路が存在します")
 
    return dist
 
edges = [(0, 1, 1), (1, 2, -3), (0, 2, 2)]
dist = bellman_ford(3, edges, 0)
print(f"最短距離: {dist}")  # [0, 1, -2]

def min_coins_japan(amount: int) -> dict:
    """日本の硬貨でお釣りを最小枚数にする"""
    coins = [500, 100, 50, 10, 5, 1]
    result = {}
    remaining = amount
 
    for coin in coins:
        if remaining >= coin:
            count = remaining // coin
            result[coin] = count
            remaining -= coin * count
 
    return result
 
# テスト
change = min_coins_japan(1376)
print(f"1376円のお釣り: {change}")
# {500: 2, 100: 3, 50: 1, 10: 2, 5: 1, 1: 1}
total_coins = sum(change.values())
print(f"合計枚数: {total_coins}")  # 10

def max_meetings(meetings: list) -> list:
    """会議室割り当て問題（活動選択問題の応用）"""
    indexed = [(end, start, i) for i, (start, end) in enumerate(meetings)]
    indexed.sort()
 
    selected = []
    last_end = -1
 
    for end, start, idx in indexed:
        if start >= last_end:
            selected.append((idx, start, end))
            last_end = end
 
    return selected
 
meetings = [(0, 6), (1, 4), (3, 5), (5, 7), (5, 9), (8, 9)]
result = max_meetings(meetings)
print(f"開催可能な会議数: {len(result)}")
for idx, s, e in result:
    print(f"  会議{idx}: {s}-{e}")
# 会議1: 1-4, 会議3: 5-7, 会議5: 8-9 → 3会議

def assign_cookies(children: list, cookies: list) -> int:
    """飴の配分問題 - O(n log n + m log m)
    children: 各子供の満足度閾値
    cookies: 各飴のサイズ
    """
    children_sorted = sorted(children)
    cookies_sorted = sorted(cookies)
 
    child_i = 0
    cookie_i = 0
 
    while child_i < len(children_sorted) and cookie_i < len(cookies_sorted):
        if cookies_sorted[cookie_i] >= children_sorted[child_i]:
            child_i += 1  # この子供は満足
        cookie_i += 1  # 次の飴へ
 
    return child_i
 
children = [1, 2, 3]
cookies = [1, 1]
print(f"満足する子供の数: {assign_cookies(children, cookies)}")  # 1
 
children = [1, 2]
cookies = [1, 2, 3]
print(f"満足する子供の数: {assign_cookies(children, cookies)}")  # 2

def min_platforms(arrivals: list, departures: list) -> int:
    """最小プラットフォーム数 - O(n log n)
    イベントソートによる貪欲法
    """
    events = []
    for a in arrivals:
        events.append((a, 1))   # 到着: +1
    for d in departures:
        events.append((d, -1))  # 出発: -1
 
    events.sort(key=lambda x: (x[0], x[1]))  # 同時刻なら出発を先に
 
    current = 0
    max_platforms = 0
 
    for _, event_type in events:
        current += event_type
        max_platforms = max(max_platforms, current)
 
    return max_platforms
 
arrivals   = [900, 940, 950, 1100, 1500, 1800]
departures = [910, 1200, 1120, 1130, 1900, 2000]
print(f"最小プラットフォーム数: {min_platforms(arrivals, departures)}")  # 3

def smallest_string_by_appending(s: str) -> str:
    """辞書順最小の文字列を構築する貪欲法 - O(n²)
    各文字を先頭か末尾に追加する
    """
    from collections import deque
    result = deque()
 
    for char in s:
        if result and char < result[0]:
            result.appendleft(char)
        else:
            result.append(char)
 
    return ''.join(result)
 
# より洗練された解法: 残りの文字列との比較
def smallest_string_precise(s: str) -> str:
    """辞書順最小の文字列を構築（正確版）- O(n²)"""
    from collections import deque
    result = deque()
    n = len(s)
    left = 0
    right = n - 1
 
    chars = list(s)
 
    while left <= right:
        if chars[left] < chars[right]:
            result.append(chars[left])
            left += 1
        elif chars[left] > chars[right]:
            result.append(chars[right])
            right -= 1
        else:
            # 同じ場合は内側を比較して決定
            l, r = left, right
            while l < r and chars[l] == chars[r]:
                l += 1
                r -= 1
            if l >= r or chars[l] < chars[r]:
                result.append(chars[left])
                left += 1
            else:
                result.append(chars[right])
                right -= 1
 
    return ''.join(result)
 
print(smallest_string_by_appending("ACBDFE"))
print(smallest_string_precise("CBABC"))  # "BAACC" ではなく正しい辞書順最小

def min_groups(intervals: list) -> int:
    """区間の最小グループ分け - O(n log n)
    最大同時重なり数を求める（= 最小グループ数 = 区間グラフの彩色数）
    """
    events = []
    for start, end in intervals:
        events.append((start, 1))
        events.append((end, -1))
 
    events.sort(key=lambda x: (x[0], x[1]))
 
    current = 0
    max_overlap = 0
    for _, delta in events:
        current += delta
        max_overlap = max(max_overlap, current)
 
    return max_overlap
 
intervals = [(1, 5), (2, 6), (4, 7), (6, 8), (7, 10)]
print(f"最小グループ数: {min_groups(intervals)}")  # 3

def bipartite_matching_as_matroid_intersection(
    left_nodes: list, right_nodes: list, edges: list
) -> list:
    """二部マッチング（マトロイド交差の具体例）
    ここでは増加路法で実装（マトロイド交差の特殊ケース）
    """
    match_left = {}
    match_right = {}
 
    def augment(u, visited):
        for v in adj[u]:
            if v not in visited:
                visited.add(v)
                if v not in match_right or augment(match_right[v], visited):
                    match_left[u] = v
                    match_right[v] = u
                    return True
        return False
 
    adj = {u: [] for u in left_nodes}
    for u, v in edges:
        adj[u].append(v)
 
    for u in left_nodes:
        augment(u, set())
 
    return list(match_left.items())
 
left = ['a', 'b', 'c']
right = ['x', 'y', 'z']
edges = [('a','x'), ('a','y'), ('b','x'), ('b','z'), ('c','y')]
matching = bipartite_matching_as_matroid_intersection(left, right, edges)
print(f"最大マッチング: {matching}")
print(f"マッチングサイズ: {len(matching)}")
# マトロイド交差の理論により、貪欲法の一般化で解ける

import random
import math
 
def secretary_problem_strategy(candidates: list) -> tuple:
    """セクレタリー問題の最適戦略（1/e 戦略）
    最初の n/e 人を観察のみ（基準値の設定）
    以降、基準値を超えた最初の候補者を採用
 
    最良の候補者を選ぶ確率は 1/e ≒ 36.8% に収束する
    """
    n = len(candidates)
    # 最初の n/e 人を観察（探索フェーズ）
    observe_count = max(1, int(n / math.e))
 
    # 観察フェーズで最高スコアを記録
    threshold = max(candidates[:observe_count])
 
    # 決定フェーズ: 基準を超えた最初の候補者を採用
    for i in range(observe_count, n):
        if candidates[i] > threshold:
            return candidates[i], i, True  # (スコア, インデックス, 採用した)
 
    # 誰も基準を超えなければ最後の候補者を採用
    return candidates[-1], n - 1, False
 
# シミュレーション
def simulate_secretary(n: int, trials: int = 10000) -> float:
    """セクレタリー問題のシミュレーション"""
    successes = 0
 
    for _ in range(trials):
        candidates = list(range(1, n + 1))
        random.shuffle(candidates)
        best = max(candidates)
 
        chosen, _, _ = secretary_problem_strategy(candidates)
        if chosen == best:
            successes += 1
 
    return successes / trials
 
random.seed(42)
for n in [10, 50, 100, 1000]:
    success_rate = simulate_secretary(n)
    print(f"n={n:4d}: 成功率 = {success_rate:.3f} (理論値 ≒ {1/math.e:.3f})")

def ski_rental_deterministic(daily_rent: int, purchase_price: int,
                              actual_days: int) -> dict:
    """スキーレンタル問題の決定的戦略
    break-even 日（p/r 日目）にレンタルから購入に切り替える
    競合比: 2 - r/p（最悪ケースで最適解の2倍以内）
    """
    break_even = purchase_price // daily_rent
 
    # 戦略: break_even 日目に購入
    if actual_days <= break_even:
        # 購入前に終了 → レンタルのみ
        online_cost = actual_days * daily_rent
    else:
        # break_even 日レンタル + 購入
        online_cost = break_even * daily_rent + purchase_price
 
    # 最適解（事後的に判断）
    optimal_cost = min(actual_days * daily_rent, purchase_price)
 
    return {
        'online_cost': online_cost,
        'optimal_cost': optimal_cost,
        'competitive_ratio': online_cost / optimal_cost if optimal_cost > 0 else float('inf'),
        'strategy': f"{'レンタル' if actual_days <= break_even else f'{break_even}日目に購入'}"
    }
 
# 使用例
rent = 100
price = 1000
 
for days in [5, 10, 15, 20, 50]:
    result = ski_rental_deterministic(rent, price, days)
    print(f"日数={days:2d}: オンライン={result['online_cost']:5d}, "
          f"最適={result['optimal_cost']:5d}, "
          f"競合比={result['competitive_ratio']:.2f}, "
          f"戦略={result['strategy']}")

import itertools
 
def verify_greedy(greedy_func, brute_force_func, test_cases):
    """貪欲法の結果を全探索と比較して検証"""
    for i, test_input in enumerate(test_cases):
        greedy_result = greedy_func(test_input)
        bf_result = brute_force_func(test_input)
        if greedy_result != bf_result:
            print(f"反例発見! テスト{i}: 入力={test_input}")
            print(f"  貪欲: {greedy_result}")
            print(f"  全探索: {bf_result}")
            return False
    print("全テスト合格")
    return True