def linear_search(arr: list, target) -> int:
    """
    線形探索: 先頭から順に要素を走査する。
 
    Args:
        arr: 探索対象のリスト（ソート不要）
        target: 探索する値
 
    Returns:
        見つかった場合はインデックス、見つからなければ -1
 
    計算量: O(n) 時間, O(1) 空間
    """
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1
 
 
# --- 使用例 ---
data = [4, 2, 7, 1, 9, 3, 8, 5]
 
print(linear_search(data, 9))   # => 4  (インデックス4に存在)
print(linear_search(data, 6))   # => -1 (存在しない)

def sentinel_linear_search(arr: list, target) -> int:
    """
    番兵法による線形探索。
    配列末尾に target を番兵として追加し、境界チェックを不要にする。
 
    注意: 元配列を一時的に変更するため、スレッドセーフではない。
 
    計算量: O(n) 時間（定数倍の改善）, O(1) 空間
    """
    n = len(arr)
    if n == 0:
        return -1
 
    # 末尾を退避して番兵を設置
    last = arr[n - 1]
    arr[n - 1] = target
 
    i = 0
    while arr[i] != target:
        i += 1
 
    # 末尾を復元
    arr[n - 1] = last
 
    # 最後に見つかった位置が元の末尾かどうかを判別
    if i < n - 1 or arr[n - 1] == target:
        return i
    return -1
 
 
# --- 動作の可視化 ---
# arr = [4, 2, 7, 1, 9], target = 7
#
# 番兵設置後: [4, 2, 7, 1, 7]  ← 末尾に7を配置
#
# i=0: arr[0]=4 != 7 → 次へ
# i=1: arr[1]=2 != 7 → 次へ
# i=2: arr[2]=7 == 7 → ループ終了！
#
# i=2 < n-1=4 なので、元の配列で見つかったと判定
# 復元: [4, 2, 7, 1, 9]
# return 2

def find_all(arr: list, target) -> list[int]:
    """
    target と一致する全てのインデックスを返す。
 
    Returns:
        一致するインデックスのリスト（空リストは不在を意味する）
 
    計算量: O(n) 時間, O(k) 空間（k = 一致数）
    """
    return [i for i, val in enumerate(arr) if val == target]
 
 
# --- 使用例 ---
data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(find_all(data, 5))   # => [4, 8, 10]
print(find_all(data, 7))   # => []

def find_first_match(arr: list, predicate) -> int:
    """
    与えられた条件を最初に満たす要素のインデックスを返す。
 
    Args:
        predicate: 要素を受け取りboolを返す関数
 
    計算量: O(n) 時間, O(1) 空間
    """
    for i, val in enumerate(arr):
        if predicate(val):
            return i
    return -1
 
 
# --- 使用例 ---
students = [
    {"name": "Alice", "score": 72},
    {"name": "Bob", "score": 95},
    {"name": "Charlie", "score": 88},
]
# スコア90以上の最初の学生
idx = find_first_match(students, lambda s: s["score"] >= 90)
print(students[idx]["name"])  # => "Bob"

def binary_search(arr: list, target) -> int:
    """
    二分探索: ソート済み配列で target を探す。
 
    Args:
        arr: ソート済みリスト（昇順）
        target: 探索する値
 
    Returns:
        見つかった場合はインデックス、見つからなければ -1
 
    計算量: O(log n) 時間, O(1) 空間
    """
    left, right = 0, len(arr) - 1
 
    while left <= right:
        mid = left + (right - left) // 2  # オーバーフロー防止の定石
 
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
 
    return -1

def binary_search_recursive(arr: list, target, left: int = 0,
                             right: int = None) -> int:
    """
    二分探索の再帰版。
 
    計算量: O(log n) 時間, O(log n) 空間（コールスタック）
    """
    if right is None:
        right = len(arr) - 1
 
    if left > right:
        return -1
 
    mid = left + (right - left) // 2
 
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    else:
        return binary_search_recursive(arr, target, left, mid - 1)

# ================================================================
# バグ1: 中間値計算のオーバーフロー
# ================================================================
# C/C++/Java などの固定長整数で問題になる。Python は多倍長整数
# なので実害はないが、他言語への移植を考えて安全な形を使う。
 
mid = (left + right) // 2           # 非推奨: left + right がオーバーフローする可能性
mid = left + (right - left) // 2    # 推奨: 安全な計算
 
# ================================================================
# バグ2: 無限ループ
# ================================================================
# left = 3, right = 4, mid = 3 のとき:
#   arr[mid] < target → left = mid   ← 進まない！無限ループ
#   正しくは: left = mid + 1
 
# ================================================================
# バグ3: off-by-one エラー（ループ条件）
# ================================================================
# while left < right   → 探索範囲に left == right の場合を含まない
# while left <= right  → 探索範囲に left == right の場合を含む
# どちらを使うかで、更新式とセットで正しさが変わる
 
# ================================================================
# バグ4: 右端の初期値
# ================================================================
# right = len(arr)     → 範囲外アクセスの可能性
# right = len(arr) - 1 → 完全一致検索ではこちら
# right = len(arr)     → lower_bound / upper_bound ではこちら（半開区間）
 
# ================================================================
# バグ5: 等号の処理ミス
# ================================================================
# arr[mid] < target  vs  arr[mid] <= target
# lower_bound と upper_bound の違いはここだけ！
# 間違えると、重複要素がある場合に結果が異なる

# ================================================================
# テンプレートA: 完全一致探索
# ================================================================
# 用途: target と等しい要素のインデックスを返す
# ループ条件: while left <= right
# 更新: left = mid + 1, right = mid - 1
# 初期値: left = 0, right = len(arr) - 1
# 終了: target が見つかれば mid を返す。見つからなければ -1
 
def search_exact(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1
 
# ================================================================
# テンプレートB: 境界探索（lower_bound / upper_bound）
# ================================================================
# 用途: 条件を満たす最小（または最大）のインデックスを返す
# ループ条件: while left < right
# 更新: left = mid + 1 または right = mid（方向による）
# 初期値: left = 0, right = len(arr)（半開区間 [left, right) ）
# 終了: left == right となった位置が答え

import bisect
 
 
def lower_bound(arr: list, target) -> int:
    """
    target 以上の最小のインデックスを返す（leftmost insertion point）。
 
    全要素が target 未満の場合は len(arr) を返す。
    Python 標準ライブラリでは bisect.bisect_left に相当する。
 
    例: arr = [1, 3, 3, 3, 5, 7], target = 3
        → return 1（最初の 3 のインデックス）
 
    計算量: O(log n) 時間, O(1) 空間
    """
    left, right = 0, len(arr)
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left
 
 
def upper_bound(arr: list, target) -> int:
    """
    target より大きい最小のインデックスを返す（rightmost insertion point）。
 
    全要素が target 以下の場合は len(arr) を返す。
    Python 標準ライブラリでは bisect.bisect_right に相当する。
 
    例: arr = [1, 3, 3, 3, 5, 7], target = 3
        → return 4（最後の 3 の次のインデックス）
 
    計算量: O(log n) 時間, O(1) 空間
    """
    left, right = 0, len(arr)
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] <= target:    # ← lower_bound との唯一の違い
            left = mid + 1
        else:
            right = mid
    return left
 
 
# --- lower_bound と upper_bound の関係 ---
# arr = [1, 3, 3, 3, 5, 7]
#
#  idx:  0  1  2  3  4  5
#  val:  1  3  3  3  5  7
#           ^        ^
#           |        |
#     lower_bound=1  upper_bound=4
#
# target=3 の個数 = upper_bound - lower_bound = 4 - 1 = 3
 
def count_occurrences(arr: list, target) -> int:
    """ソート済み配列で target の出現回数を O(log n) で数える。"""
    return upper_bound(arr, target) - lower_bound(arr, target)
 
 
# --- bisect モジュールの活用 ---
arr = [1, 3, 3, 3, 5, 7]
 
# lower_bound
print(bisect.bisect_left(arr, 3))   # => 1
 
# upper_bound
print(bisect.bisect_right(arr, 3))  # => 4
 
# target の出現回数
print(bisect.bisect_right(arr, 3) - bisect.bisect_left(arr, 3))  # => 3
 
# ソート順を維持した挿入
bisect.insort(arr, 4)
print(arr)  # => [1, 3, 3, 3, 4, 5, 7]

def max_rope_length(ropes: list[int], k: int) -> int:
    """
    n 本のロープを切って k 本以上の同じ長さのロープを作る。
    最大で何 cm の長さにできるか？
 
    例: ropes = [802, 743, 457, 539], k = 11
    → answer = 200（200cm のロープが合計 11 本取れる）
 
    アプローチ:
    - 答え（ロープの長さ）の範囲は [1, max(ropes)]
    - ある長さ L で切ったとき k 本以上取れるかを判定
    - 判定関数は単調減少（L が大きいほど取れる本数は減る）
    - → 条件を満たす最大の L を二分探索
 
    計算量: O(n * log(max(ropes))) 時間, O(1) 空間
    """
    def can_cut(length: int) -> bool:
        """長さ length で切ったとき k 本以上取れるか？"""
        return sum(r // length for r in ropes) >= k
 
    left, right = 1, max(ropes)
    result = 0
 
    while left <= right:
        mid = left + (right - left) // 2
        if can_cut(mid):
            result = mid        # 条件を満たすので、もっと大きくできるか試す
            left = mid + 1
        else:
            right = mid - 1     # 条件を満たさないので、小さくする
 
    return result
 
 
# --- 動作例 ---
ropes = [802, 743, 457, 539]
print(max_rope_length(ropes, 11))  # => 200
 
# 判定の様子:
# L=401: 802//401 + 743//401 + 457//401 + 539//401 = 2+1+1+1 = 5 < 11 → NG
# L=200: 802//200 + 743//200 + 457//200 + 539//200 = 4+3+2+2 = 11 >= 11 → OK
# L=201: 802//201 + 743//201 + 457//201 + 539//201 = 3+3+2+2 = 10 < 11 → NG
# → answer = 200

def search_rotated(arr: list, target) -> int:
    """
    回転ソート済み配列で target を探す。
 
    回転ソート済み配列とは、ソート済み配列をある位置で分割し、
    前後を入れ替えたもの。
    例: [0,1,2,4,5,6,7] → [4,5,6,7,0,1,2]（インデックス3で回転）
 
    ポイント: mid で分割すると、少なくとも片方はソート済み。
    ソート済みの方で target が範囲内にあるかを判定する。
 
    計算量: O(log n) 時間, O(1) 空間
    """
    left, right = 0, len(arr) - 1
 
    while left <= right:
        mid = left + (right - left) // 2
 
        if arr[mid] == target:
            return mid
 
        # 左半分がソート済みかを判定
        if arr[left] <= arr[mid]:
            # target が左半分の範囲内にあるか
            if arr[left] <= target < arr[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            # 右半分がソート済み
            # target が右半分の範囲内にあるか
            if arr[mid] < target <= arr[right]:
                left = mid + 1
            else:
                right = mid - 1
 
    return -1
 
 
# --- 動作例 ---
# arr = [4, 5, 6, 7, 0, 1, 2], target = 0
#
# Step 1: left=0, right=6, mid=3
#   arr[0]=4 <= arr[3]=7 → 左半分 [4,5,6,7] はソート済み
#   4 <= 0 < 7 ? No → target は右半分にある → left = 4
#
# Step 2: left=4, right=6, mid=5
#   arr[4]=0 <= arr[5]=1 → 左半分 [0,1] はソート済み
#   0 <= 0 < 1 ? Yes → right = 4
#
# Step 3: left=4, right=4, mid=4
#   arr[4]=0 == 0 → 発見！ return 4

def find_peak_element(arr: list) -> int:
    """
    配列内のピーク要素（両隣より大きい要素）のインデックスを返す。
 
    arr[-1] = arr[n] = -∞ と仮定する。
    ピーク要素が複数ある場合、どれか1つを返せばよい。
 
    ポイント: arr[mid] < arr[mid+1] なら右側にピークが存在する。
    （上り坂の先には必ず山頂がある）
 
    計算量: O(log n) 時間, O(1) 空間
    """
    left, right = 0, len(arr) - 1
 
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] < arr[mid + 1]:
            left = mid + 1     # 右側にピークがある
        else:
            right = mid        # 左側（mid含む）にピークがある
 
    return left
 
 
# --- 動作例 ---
print(find_peak_element([1, 3, 5, 4, 2]))  # => 2（arr[2]=5がピーク）
print(find_peak_element([1, 2, 3, 4, 5]))  # => 4（単調増加なら末尾）

def integer_sqrt(n: int) -> int:
    """
    非負整数 n の整数平方根を求める（切り捨て）。
 
    x * x <= n を満たす最大の x を二分探索で求める。
 
    計算量: O(log n) 時間, O(1) 空間
    """
    if n < 2:
        return n
 
    left, right = 1, n // 2
    result = 1
 
    while left <= right:
        mid = left + (right - left) // 2
        if mid * mid == n:
            return mid
        elif mid * mid < n:
            result = mid
            left = mid + 1
        else:
            right = mid - 1
 
    return result
 
 
# --- 検証 ---
print(integer_sqrt(16))   # => 4
print(integer_sqrt(27))   # => 5（5*5=25 <= 27 < 36=6*6）
print(integer_sqrt(100))  # => 10

class HashTable:
    """
    チェイニング方式のハッシュテーブル実装。
 
    特徴:
    - 動的リサイズ（ロードファクター 0.75 超で 2 倍に拡張）
    - 挿入・探索・削除をサポート
    """
 
    def __init__(self, initial_capacity: int = 16):
        self._capacity = initial_capacity
        self._size = 0
        self._buckets: list[list] = [[] for _ in range(self._capacity)]
        self._load_factor_threshold = 0.75
 
    def _hash(self, key) -> int:
        """キーのハッシュ値をバケットインデックスに変換する。"""
        return hash(key) % self._capacity
 
    def put(self, key, value) -> None:
        """キーと値のペアを挿入する。既存キーは値を更新する。"""
        if self._size / self._capacity > self._load_factor_threshold:
            self._resize()
 
        idx = self._hash(key)
        bucket = self._buckets[idx]
 
        # 既存キーの更新チェック
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
 
        # 新規挿入
        bucket.append((key, value))
        self._size += 1
 
    def get(self, key, default=None):
        """キーに対応する値を返す。存在しなければ default を返す。"""
        idx = self._hash(key)
        for k, v in self._buckets[idx]:
            if k == key:
                return v
        return default
 
    def remove(self, key) -> bool:
        """キーを削除する。削除できたら True を返す。"""
        idx = self._hash(key)
        bucket = self._buckets[idx]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self._size -= 1
                return True
        return False
 
    def __contains__(self, key) -> bool:
        """'key in table' をサポートする。"""
        idx = self._hash(key)
        return any(k == key for k, _ in self._buckets[idx])
 
    def __len__(self) -> int:
        return self._size
 
    def _resize(self) -> None:
        """バケット数を 2 倍に拡張し、全要素を再配置する。"""
        old_buckets = self._buckets
        self._capacity *= 2
        self._buckets = [[] for _ in range(self._capacity)]
        self._size = 0
 
        for bucket in old_buckets:
            for key, value in bucket:
                self.put(key, value)
 
 
# --- 使用例 ---
ht = HashTable()
ht.put("name", "Alice")
ht.put("age", 30)
ht.put("city", "Tokyo")
 
print(ht.get("name"))     # => "Alice"
print(ht.get("age"))      # => 30
print("city" in ht)        # => True
print(len(ht))             # => 3
 
ht.remove("age")
print(ht.get("age"))       # => None
print(len(ht))             # => 2

# Python dict/set の計算量
 
# dict
d = {}
d[key] = value       # 挿入:     平均 O(1), 最悪 O(n)
value = d[key]        # 探索:     平均 O(1), 最悪 O(n)
del d[key]            # 削除:     平均 O(1), 最悪 O(n)
key in d              # 存在確認: 平均 O(1), 最悪 O(n)
 
# set
s = set()
s.add(elem)           # 追加:     平均 O(1)
elem in s             # 存在確認: 平均 O(1)
s.remove(elem)        # 削除:     平均 O(1)
s1 & s2               # 積集合:   O(min(len(s1), len(s2)))
s1 | s2               # 和集合:   O(len(s1) + len(s2))
 
# frozenset はハッシュ可能 → dict のキーや set の要素にできる
fs = frozenset([1, 2, 3])
d = {fs: "value"}     # OK

from collections import deque
 
 
def bfs(graph: dict[str, list[str]], start: str) -> list[str]:
    """
    幅優先探索: 始点から近い順に全頂点を訪問する。
 
    Args:
        graph: 隣接リスト表現のグラフ
        start: 始点のノード
 
    Returns:
        訪問順のノードリスト
 
    計算量: O(V + E) 時間, O(V) 空間
    """
    visited = set([start])
    queue = deque([start])
    order = []
 
    while queue:
        node = queue.popleft()       # キューの先頭を取り出す
        order.append(node)
 
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
 
    return order
 
 
# --- 使用例 ---
graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}
 
print(bfs(graph, "A"))
# => ['A', 'B', 'C', 'D', 'E', 'F']

from collections import deque
 
 
def bfs_shortest_path(graph: dict, start: str,
                      goal: str) -> list[str] | None:
    """
    重み無しグラフにおける最短経路を BFS で求める。
 
    Returns:
        最短経路のノードリスト。到達不能なら None。
 
    計算量: O(V + E) 時間, O(V) 空間
    """
    if start == goal:
        return [start]
 
    visited = set([start])
    queue = deque([(start, [start])])   # (現在のノード, 経路)
 
    while queue:
        node, path = queue.popleft()
 
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                new_path = path + [neighbor]
 
                if neighbor == goal:
                    return new_path
 
                visited.add(neighbor)
                queue.append((neighbor, new_path))
 
    return None  # 到達不能
 
 
# --- 使用例 ---
graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}
 
print(bfs_shortest_path(graph, "A", "F"))  # => ['A', 'C', 'F']
print(bfs_shortest_path(graph, "D", "F"))  # => ['D', 'B', 'E', 'F']

from collections import deque
 
 
def shortest_path_in_maze(maze: list[list[int]],
                          start: tuple[int, int],
                          goal: tuple[int, int]) -> int:
    """
    2Dグリッド迷路の最短経路長を BFS で求める。
 
    maze[r][c] = 0: 通行可能, 1: 壁
    上下左右の 4 方向に移動可能。
 
    Returns:
        最短ステップ数。到達不能なら -1。
    """
    rows, cols = len(maze), len(maze[0])
    if maze[start[0]][start[1]] == 1 or maze[goal[0]][goal[1]] == 1:
        return -1
 
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    visited = set([start])
    queue = deque([(start[0], start[1], 0)])  # (行, 列, ステップ数)
 
    while queue:
        r, c, steps = queue.popleft()
 
        if (r, c) == goal:
            return steps
 
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if (0 <= nr < rows and 0 <= nc < cols
                    and maze[nr][nc] == 0
                    and (nr, nc) not in visited):
                visited.add((nr, nc))
                queue.append((nr, nc, steps + 1))
 
    return -1
 
 
# --- 使用例 ---
maze = [
    [0, 0, 0, 0, 0],
    [1, 1, 0, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0],
]
print(shortest_path_in_maze(maze, (0, 0), (4, 4)))  # => 8

def dfs_recursive(graph: dict[str, list[str]], start: str,
                  visited: set = None) -> list[str]:
    """
    深さ優先探索（再帰版）。
 
    計算量: O(V + E) 時間, O(V) 空間（コールスタック）
    """
    if visited is None:
        visited = set()
 
    visited.add(start)
    order = [start]
 
    for neighbor in graph[start]:
        if neighbor not in visited:
            order.extend(dfs_recursive(graph, neighbor, visited))
 
    return order
 
 
def dfs_iterative(graph: dict[str, list[str]], start: str) -> list[str]:
    """
    深さ優先探索（反復版）。
    明示的なスタックを使い、再帰によるスタックオーバーフローを回避する。
 
    計算量: O(V + E) 時間, O(V) 空間
    """
    visited = set()
    stack = [start]
    order = []
 
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
 
        # 隣接ノードを逆順にスタックに追加
        # （元の順序で探索するため）
        for neighbor in reversed(graph[node]):
            if neighbor not in visited:
                stack.append(neighbor)
 
    return order
 
 
# --- 使用例 ---
graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}
 
print(dfs_recursive(graph, "A"))   # => ['A', 'B', 'D', 'E', 'F', 'C']
print(dfs_iterative(graph, "A"))   # => ['A', 'B', 'D', 'E', 'F', 'C']

def topological_sort(graph: dict[str, list[str]]) -> list[str]:
    """
    有向非巡回グラフ（DAG）のトポロジカルソートを DFS で求める。
 
    全てのエッジ (u, v) について、結果リスト内で u が v より前に来る。
 
    用途:
    - ビルドシステムのタスク依存解決
    - パッケージマネージャの依存関係解決
    - コンパイラの命令スケジューリング
 
    計算量: O(V + E) 時間, O(V) 空間
    """
    visited = set()
    result = []
 
    def dfs(node):
        visited.add(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                dfs(neighbor)
        result.append(node)  # 帰りがけ順で追加
 
    for node in graph:
        if node not in visited:
            dfs(node)
 
    return result[::-1]  # 逆順がトポロジカル順序
 
 
# --- 使用例: コンパイル依存関係 ---
# A → B, A → C, B → D, C → D の順に依存
dependencies = {
    "main.c":    ["utils.h", "math.h"],
    "utils.h":   ["types.h"],
    "math.h":    ["types.h"],
    "types.h":   [],
}
 
order = topological_sort(dependencies)
print(order)
# => ['types.h', 'utils.h', 'math.h', 'main.c']
# types.h を最初にコンパイルすべき

def has_cycle(graph: dict[str, list[str]]) -> bool:
    """
    有向グラフにサイクルが存在するかを DFS で判定する。
 
    3 色マーキング:
    - WHITE (未訪問): まだ訪問していない
    - GRAY  (探索中): 現在の DFS パス上にある
    - BLACK (完了):   全ての子孫を探索済み
 
    GRAY のノードに再訪問したらサイクルが存在する。
 
    計算量: O(V + E) 時間, O(V) 空間
    """
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}
 
    def dfs(node) -> bool:
        color[node] = GRAY
        for neighbor in graph.get(node, []):
            if color.get(neighbor, WHITE) == GRAY:
                return True    # サイクル検出！
            if color.get(neighbor, WHITE) == WHITE:
                if dfs(neighbor):
                    return True
        color[node] = BLACK
        return False
 
    for node in graph:
        if color[node] == WHITE:
            if dfs(node):
                return True
    return False
 
 
# --- 使用例 ---
# サイクルあり: A → B → C → A
graph_with_cycle = {"A": ["B"], "B": ["C"], "C": ["A"]}
print(has_cycle(graph_with_cycle))  # => True
 
# サイクルなし（DAG）
dag = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}
print(has_cycle(dag))  # => False

import heapq
from typing import Callable
 
 
def a_star(graph: dict, start, goal,
           h: Callable, get_neighbors: Callable) -> tuple[list, float]:
    """
    A* 探索アルゴリズム。
 
    Args:
        graph: グラフデータ（get_neighbors の実装に依存）
        start: 始点ノード
        goal: 目標ノード
        h: ヒューリスティック関数 h(node, goal) -> float
        get_neighbors: 隣接ノードとコストを返す関数
                       get_neighbors(graph, node) -> [(neighbor, cost), ...]
 
    Returns:
        (経路リスト, 総コスト) のタプル。到達不能なら ([], float('inf'))
 
    計算量: 最悪 O(b^d) 時間・空間（b=分岐数, d=深さ）
            良いヒューリスティックで大幅に削減される
    """
    # 優先度キュー: (f値, ノード)
    open_set = [(h(start, goal), 0, start)]  # (f, g, node)
    came_from = {}
    g_score = {start: 0}
    closed_set = set()
 
    while open_set:
        f, g, current = heapq.heappop(open_set)
 
        if current == goal:
            # 経路を復元
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            return path[::-1], g
 
        if current in closed_set:
            continue
        closed_set.add(current)
 
        for neighbor, cost in get_neighbors(graph, current):
            if neighbor in closed_set:
                continue
 
            tentative_g = g + cost
 
            if tentative_g < g_score.get(neighbor, float('inf')):
                g_score[neighbor] = tentative_g
                came_from[neighbor] = current
                f_score = tentative_g + h(neighbor, goal)
                heapq.heappush(open_set, (f_score, tentative_g, neighbor))
 
    return [], float('inf')  # 到達不能
 
 
# --- グリッドマップでの使用例 ---
 
def manhattan_distance(a: tuple[int, int], b: tuple[int, int]) -> int:
    """マンハッタン距離（4方向移動のヒューリスティック）。"""
    return abs(a[0] - b[0]) + abs(a[1] - b[1])
 
 
def grid_neighbors(grid: list[list[int]],
                   node: tuple[int, int]) -> list[tuple]:
    """グリッド上の隣接セル（上下左右、壁以外）を返す。"""
    rows, cols = len(grid), len(grid[0])
    r, c = node
    neighbors = []
    for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        nr, nc = r + dr, c + dc
        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0:
            neighbors.append(((nr, nc), 1))  # コスト 1
    return neighbors
 
 
# グリッドマップ（0: 通行可, 1: 壁）
grid = [
    [0, 0, 0, 0, 0],
    [1, 1, 0, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0],
]
 
path, cost = a_star(
    grid, (0, 0), (4, 4),
    h=manhattan_distance,
    get_neighbors=grid_neighbors
)
print(f"経路: {path}")  # => [(0,0), (0,1), (0,2), (1,2), (2,2), ...]
print(f"コスト: {cost}")  # => 8

import math
 
 
# --- ヒューリスティック関数の例 ---
 
def manhattan(a: tuple, b: tuple) -> float:
    """マンハッタン距離: 4方向移動に最適。"""
    return abs(a[0] - b[0]) + abs(a[1] - b[1])
 
 
def euclidean(a: tuple, b: tuple) -> float:
    """ユークリッド距離: 自由移動に最適。"""
    return math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)
 
 
def chebyshev(a: tuple, b: tuple) -> float:
    """チェビシェフ距離: 8方向移動に最適。"""
    return max(abs(a[0] - b[0]), abs(a[1] - b[1]))
 
 
def zero_heuristic(a: tuple, b: tuple) -> float:
    """ゼロヒューリスティック: ダイクストラ法と同等。"""
    return 0
 
 
# --- ヒューリスティックの強さと探索効率の関係 ---
#
# h(n) が大きいほど:
# ✓ 探索ノード数が減る（効率的）
# ✗ 最適性を失うリスクが上がる（h(n) > 真のコストの場合）
#
# h(n) が小さいほど:
# ✓ 最適解の保証が確実
# ✗ 探索ノード数が増える（非効率）
#
# 理想: h(n) = 真のコスト（計算できれば探索不要）
# 現実: 許容的な範囲で h(n) を最大化する

def two_sum_brute_force(nums: list[int], target: int) -> list[int]:
    """
    ブルートフォース: 全ペアを試す。
    計算量: O(n^2) 時間, O(1) 空間
    """
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []
 
 
def two_sum_hash(nums: list[int], target: int) -> list[int]:
    """
    ハッシュテーブルを活用: 1パスで解く。
 
    アイデア: target - nums[i] が既にハッシュマップに存在すれば、
    その要素とのペアが答えになる。
 
    計算量: O(n) 時間, O(n) 空間
    """
    seen = {}  # 値 → インデックス のマッピング
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []
 
 
def two_sum_sorted(nums: list[int], target: int) -> list[int]:
    """
    ソート済み配列の場合: 両端ポインタ法。
 
    計算量: O(n) 時間, O(1) 空間
    （ソート済みが前提。未ソートなら O(n log n) のソートが追加）
    """
    left, right = 0, len(nums) - 1
    while left < right:
        current_sum = nums[left] + nums[right]
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return []
 
 
# --- 比較 ---
nums = [2, 7, 11, 15]
target = 9
print(two_sum_brute_force(nums, target))  # => [0, 1]
print(two_sum_hash(nums, target))          # => [0, 1]
print(two_sum_sorted(nums, target))        # => [0, 1]（ソート済み前提）

def has_duplicate_linear(arr: list) -> bool:
    """
    線形探索で重複検出: O(n^2)
    """
    n = len(arr)
    for i in range(n):
        for j in range(i + 1, n):
            if arr[i] == arr[j]:
                return True
    return False
 
 
def has_duplicate_sort(arr: list) -> bool:
    """
    ソートして隣接比較: O(n log n)
    元配列を変更するため、必要なら事前にコピーする。
    """
    sorted_arr = sorted(arr)
    for i in range(len(sorted_arr) - 1):
        if sorted_arr[i] == sorted_arr[i + 1]:
            return True
    return False
 
 
def has_duplicate_hash(arr: list) -> bool:
    """
    ハッシュセットで重複検出: O(n)
    """
    seen = set()
    for val in arr:
        if val in seen:
            return True
        seen.add(val)
    return False
 
 
# --- 選択基準 ---
# n < 50 で空間を節約したい → ソート方式
# n が大きい → ハッシュ方式（最速）
# メモリ制約が厳しい → ソート方式

import bisect
 
 
def find_available_slots(events: list[tuple[int, int]],
                         query_start: int,
                         query_end: int) -> bool:
    """
    既存のイベントリスト（ソート済み）に新しいイベントを追加できるか判定する。
 
    events: [(start1, end1), (start2, end2), ...] ソート済み
    query_start, query_end: 追加したいイベントの時間帯
 
    アプローチ: 二分探索で挿入位置を特定し、前後のイベントと重なるかをチェック。
 
    計算量: O(log n) 時間
    """
    starts = [e[0] for e in events]
 
    # query_start 以上の最小のイベントのインデックス
    idx = bisect.bisect_left(starts, query_start)
 
    # 右隣のイベントと重なるかチェック
    if idx < len(events) and events[idx][0] < query_end:
        return False
 
    # 左隣のイベントと重なるかチェック
    if idx > 0 and events[idx - 1][1] > query_start:
        return False
 
    return True
 
 
# --- 使用例 ---
events = [(1, 3), (5, 8), (10, 15), (18, 20)]
print(find_available_slots(events, 3, 5))    # => True（空き）
print(find_available_slots(events, 4, 6))    # => False（[5,8]と重なる）
print(find_available_slots(events, 15, 18))  # => True（空き）

import hashlib
from typing import Any
 
 
class BloomFilter:
    """
    ブルームフィルタ: 集合に要素が「確実に含まれない」ことを
    高速に判定する確率的データ構造。
 
    特性:
    - 偽陽性（False Positive）: あり得る
    - 偽陰性（False Negative）: あり得ない
    - 空間効率: ハッシュテーブルより遥かに小さい
 
    用途:
    - スペルチェッカ: 辞書に無い単語の高速判定
    - キャッシュ: 存在しないキーへの不要な DB アクセスの回避
    - ネットワーク: ルーティングテーブルのフィルタリング
    """
 
    def __init__(self, size: int = 1000, num_hashes: int = 3):
        self._size = size
        self._num_hashes = num_hashes
        self._bit_array = [False] * size
 
    def _hashes(self, item: Any) -> list[int]:
        """item に対して複数のハッシュ値を生成する。"""
        result = []
        for i in range(self._num_hashes):
            h = hashlib.sha256(f"{item}:{i}".encode()).hexdigest()
            result.append(int(h, 16) % self._size)
        return result
 
    def add(self, item: Any) -> None:
        """要素を追加する。"""
        for idx in self._hashes(item):
            self._bit_array[idx] = True
 
    def might_contain(self, item: Any) -> bool:
        """
        要素が含まれる可能性があるかを判定する。
 
        Returns:
            True: 含まれる可能性がある（偽陽性の可能性あり）
            False: 確実に含まれない（偽陰性なし）
        """
        return all(self._bit_array[idx] for idx in self._hashes(item))
 
 
# --- 使用例: Webクローラのフィルタリング ---
visited = BloomFilter(size=10000, num_hashes=5)
 
urls = [
    "https://example.com/page1",
    "https://example.com/page2",
    "https://example.com/page3",
]
 
for url in urls:
    visited.add(url)
 
# 判定
print(visited.might_contain("https://example.com/page1"))  # => True
print(visited.might_contain("https://example.com/page4"))  # => False（確実に未追加）

# --- Python 探索の最適化テクニック ---
 
# 1. in 演算子の使い分け
# my_list = [1, 2, 3, ..., 100000]  # リスト: in は O(n)
# my_set = set(my_list)              # セット: in は O(1)
 
# 大量の存在確認は set を使う
# 5 in my_list   # O(n) — 遅い
# 5 in my_set    # O(1) — 速い
 
# 2. dict.get() vs try/except
d = {"key": "value"}
 
# get() は KeyError を出さない（探索のオーバーヘッドが小さい）
result = d.get("missing_key", "default")
 
# try/except は存在する場合は高速だが、存在しない場合は遅い
# （例外処理のコストが高い）
 
# 3. bisect は C 実装で高速
import bisect
# bisect.bisect_left() は C で実装されており、
# Python で書いた二分探索より数倍高速
 
# 4. collections.deque は BFS に最適
from collections import deque
# deque.popleft() は O(1)
# list.pop(0) は O(n)（先頭削除で全要素をシフト）
 
# 5. sorted() + bisect vs set
# 範囲検索が必要 → sorted list + bisect
# 存在確認のみ → set
# 両方必要 → SortedList (sortedcontainers パッケージ)

# --- NG パターン ---
# 10万件のユーザリストから毎回線形探索
def find_user_by_email_bad(users: list[dict], email: str) -> dict | None:
    """
    問題: リクエストのたびに O(n) の探索が走る。
    1秒あたり1000リクエスト × 10万件 = 1億回の比較/秒
    """
    for user in users:
        if user["email"] == email:
            return user
    return None
 
 
# --- OK パターン ---
# 起動時にインデックスを構築し、O(1) で探索
def build_user_index(users: list[dict]) -> dict[str, dict]:
    """O(n) で一度だけインデックスを構築する。"""
    return {user["email"]: user for user in users}
 
user_index = build_user_index(users)
 
def find_user_by_email_good(email: str) -> dict | None:
    """O(1) で探索。"""
    return user_index.get(email)
 
# 判断基準:
# - 検索が 1 回だけ → 線形探索で十分
# - 検索が繰り返される → インデックス構築 + O(1) 探索
# - データが頻繁に変更 → 更新コストとのバランスを考える

# --- NG パターン ---
class BadHashTable:
    """悪いハッシュ関数の例: 全ての文字列が同じバケットに入る可能性。"""
 
    def _hash(self, key: str) -> int:
        # 文字列長でハッシュ → 同じ長さの文字列は全て衝突
        return len(key) % self._capacity
 
 
# --- NG パターン2 ---
class AnotherBadHashTable:
    """別の悪い例: 先頭文字のみでハッシュ。"""
 
    def _hash(self, key: str) -> int:
        # 先頭文字の ASCII 値 → "apple", "avocado", "apricot" が全て衝突
        return ord(key[0]) % self._capacity
 
 
# --- OK パターン ---
class GoodHashTable:
    """Python 組み込みの hash() を使う（SipHash ベース）。"""
 
    def _hash(self, key) -> int:
        return hash(key) % self._capacity
 
# 教訓:
# - 自前のハッシュ関数を作らない（言語標準のものを使う）
# - ハッシュ関数はキーの全情報を使うべき
# - セキュリティが重要な場面では暗号学的ハッシュ関数を使う

# --- NG パターン ---
# BFS は重み無しグラフでのみ最短経路を保証する。
# 辺に異なる重みがある場合、BFS は最適解を返さない。
#
# 例: A→B(コスト1), A→C(コスト5), B→C(コスト1)
# BFS: A→C (コスト5) を最短と判定する可能性がある
# 正解: A→B→C (コスト2) が最短
 
# --- OK パターン ---
# 重み付きグラフではダイクストラ法または A* を使用する。
import heapq
 
def dijkstra(graph: dict, start: str) -> dict[str, float]:
    """ダイクストラ法: 重み付きグラフの最短経路。"""
    dist = {start: 0}
    pq = [(0, start)]
 
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist.get(u, float('inf')):
            continue
        for v, w in graph.get(u, []):
            nd = d + w
            if nd < dist.get(v, float('inf')):
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
 
    return dist

# --- NG パターン ---
data = [3, 1, 4, 1, 5, 9, 2, 6]  # ソートされていない！
result = binary_search(data, 5)    # 不正な結果を返す可能性大
 
# --- OK パターン ---
# 方法1: 事前にソートする
data.sort()  # O(n log n)
result = binary_search(data, 5)    # 正しい結果
 
# 方法2: ソート済みを仮定できない場合は線形探索を使う
result = linear_search(data, 5)
 
# 方法3: 頻繁に検索するなら、ソート済みリストを維持する
import bisect
sorted_data = sorted(data)  # 初回のみ O(n log n)
bisect.insort(sorted_data, new_element)  # 挿入時に O(n)（シフトが発生）
# 挿入が多い場合は SortedList (sortedcontainers) を検討

assert find_min([5, 3, 8, 1, 9, 2]) == 3
assert find_last([1, 3, 5, 3, 7, 3], 3) == 5
assert count_if([1, 2, 3, 4, 5, 6], lambda x: x % 2 == 0) == 3

arr = [1, 2, 2, 3, 3, 3, 4, 5, 5]
assert binary_search(arr, 3) in [3, 4, 5]  # いずれかの 3 のインデックス
assert lower_bound(arr, 3) == 3
assert upper_bound(arr, 3) == 6
assert count_in_range(arr, 2, 4) == 6  # [2,2,3,3,3,4] の6個