# パターン1: O(1) — 定数時間
def get_first(arr):
    return arr[0]  # インデックスアクセスは O(1)
 
# パターン2: O(n) — 線形時間
def sum_array(arr):
    total = 0
    for x in arr:      # n回ループ
        total += x     # O(1) の操作
    return total
# → O(n)
 
# パターン3: O(n²) — 二重ループ
def has_duplicate(arr):
    n = len(arr)
    for i in range(n):       # n回
        for j in range(i+1, n):  # 最大 n-1 回
            if arr[i] == arr[j]:
                return True
    return False
# → O(n × n) = O(n²)
 
# パターン4: O(log n) — 半分に分割
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1     # 探索範囲が半分に
        else:
            right = mid - 1    # 探索範囲が半分に
    return -1
# → 毎回半分 → log₂(n) 回で終了 → O(log n)
 
# パターン5: O(n log n) — 分割統治
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])    # T(n/2)
    right = merge_sort(arr[mid:])   # T(n/2)
    return merge(left, right)       # O(n)
# T(n) = 2T(n/2) + O(n) → O(n log n)

# ケース1: 独立したループ → 加算
def example1(arr):
    n = len(arr)
 
    # ループ1: O(n)
    for i in range(n):
        process(arr[i])
 
    # ループ2: O(n)
    for i in range(n):
        process(arr[i])
 
    # 合計: O(n) + O(n) = O(2n) = O(n)
    # → 定数倍は無視
 
# ケース2: ネストしたループ → 乗算
def example2(arr):
    n = len(arr)
    for i in range(n):        # n回
        for j in range(n):    # n回
            process(arr[i], arr[j])
    # 合計: O(n × n) = O(n²)
 
# ケース3: 内側ループがiに依存
def example3(arr):
    n = len(arr)
    for i in range(n):
        for j in range(i):    # i回（0, 1, 2, ..., n-1）
            process(arr[i], arr[j])
    # 合計: 0 + 1 + 2 + ... + (n-1) = n(n-1)/2 = O(n²)
 
# ケース4: ループ変数が倍増
def example4(n):
    i = 1
    while i < n:
        process(i)
        i *= 2  # 1, 2, 4, 8, 16, ...
    # 何回ループする？ 2^k = n → k = log₂(n)
    # 合計: O(log n)
 
# ケース5: ループ変数が平方根に
def example5(n):
    i = n
    while i > 1:
        process(i)
        i = int(i ** 0.5)  # n, √n, n^(1/4), n^(1/8), ...
    # 2^(2^k) = n → k = log₂(log₂(n))
    # 合計: O(log log n)
 
# ケース6: 二重ループだが合計はO(n)
def example6(arr):
    """2ポインタの典型例"""
    n = len(arr)
    j = 0
    for i in range(n):         # n回
        while j < n and arr[j] < arr[i]:
            j += 1             # jは全体でn回しか増えない
    # 外側ループ: n回、j の増加: 合計n回
    # 合計: O(n + n) = O(n) ← O(n²)ではない！
 
# ケース7: 再帰でのO(2^n)
def example7(n):
    """フィボナッチの素朴な再帰"""
    if n <= 1:
        return n
    return example7(n-1) + example7(n-2)
    # T(n) = T(n-1) + T(n-2) + O(1)
    # T(n) ≈ 2T(n-1) → O(2^n)
    # 正確には O(φ^n) where φ = (1+√5)/2 ≈ 1.618

# 動的配列（Python list）の append は O(1)?
 
# 実際の動作:
# - 容量に余裕がある場合: O(1)
# - 容量が足りない場合: O(n)（新しい配列にコピー）
 
# 償却分析:
# n回の append での総コスト:
# 1, 1, 1, ..., 1, n, 1, 1, ..., 1, 2n, ...
#                  ↑ リサイズ          ↑ リサイズ
#
# 容量を2倍に拡張する場合:
# 総コスト = n + (1 + 2 + 4 + ... + n) = n + 2n = 3n
# 1回あたり = 3n / n = O(1)（償却）
#
# → 個々の操作はO(1)〜O(n)だが、
#   n回の操作全体で見るとO(n) → 1回あたりO(1)
 
# 他の償却O(1)の例:
# - ハッシュテーブルの挿入（リハッシュ時にO(n)）
# - Union-Find の操作（経路圧縮+ランク付き）
# - 二進カウンタのインクリメント

# 空間計算量: アルゴリズムが使用する追加メモリ量
 
# O(1) 空間: 入力以外に固定量のメモリ
def find_max(arr):
    max_val = arr[0]  # 変数1つだけ
    for x in arr:
        if x > max_val:
            max_val = x
    return max_val
# 空間: O(1) — max_val のみ
 
# O(n) 空間: 入力に比例するメモリ
def reverse_array(arr):
    result = []        # 新しい配列
    for x in reversed(arr):
        result.append(x)
    return result
# 空間: O(n) — result 配列
 
# O(n) 空間 (再帰のスタック)
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)
# 空間: O(n) — 再帰の深さが n（スタックフレーム n 個）
 
# O(log n) 空間
# マージソートの再帰の深さ: O(log n)
# ただし配列のコピーで O(n) 空間が必要
 
# 時間と空間のトレードオフ:
# 例: 重複チェック
# 方法1: O(n²) 時間, O(1) 空間 — 全ペア比較
# 方法2: O(n) 時間, O(n) 空間 — ハッシュセット使用
# → メモリを使って速度を買う

# 例1: インプレース vs 非インプレース
 
# 非インプレース: O(n) 追加空間
def sorted_copy(arr):
    return sorted(arr)  # 新しいリストを作成
 
# インプレース: O(1) 追加空間
def sort_inplace(arr):
    arr.sort()  # 元のリストを変更
 
# 例2: 再帰の空間計算量
 
# O(n) 空間 — 再帰が深い
def sum_recursive(arr, n):
    if n == 0:
        return 0
    return arr[n-1] + sum_recursive(arr, n-1)
# コールスタック: n フレーム
 
# O(log n) 空間 — 再帰が浅い
def sum_divide(arr, left, right):
    if left == right:
        return arr[left]
    mid = (left + right) // 2
    return sum_divide(arr, left, mid) + sum_divide(arr, mid+1, right)
# コールスタック: log₂(n) フレーム
 
# 例3: 末尾再帰最適化（TCO）
# 一部の言語（Scheme, Scala等）では末尾再帰をO(1)空間に最適化
def factorial_tail(n, acc=1):
    if n <= 1:
        return acc
    return factorial_tail(n - 1, n * acc)  # 末尾位置の再帰呼び出し
# Pythonは末尾再帰最適化をサポートしない
# → iterativeに書き直すのが一般的
 
# 例4: DPの空間最適化
# 通常のDP: O(n × m)
def lcs_full(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]
# 空間: O(m × n)
 
# 空間最適化DP: O(min(m, n))
def lcs_optimized(s1, s2):
    if len(s1) < len(s2):
        s1, s2 = s2, s1
    m, n = len(s1), len(s2)
    prev = [0] * (n + 1)
    curr = [0] * (n + 1)
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                curr[j] = prev[j-1] + 1
            else:
                curr[j] = max(prev[j], curr[j-1])
        prev, curr = curr, [0] * (n + 1)
    return prev[n]
# 空間: O(n) — 2行分だけ保持

# O(n²) → O(n) に改善する定番パターン
 
# パターン1: ハッシュマップで探索を O(1) に
# 問題: 配列から合計が target になるペアを見つける
 
# ❌ O(n²): 全ペア探索
def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
 
# ✅ O(n): ハッシュマップ
def two_sum_hash(nums, target):
    seen = {}  # 値 → インデックス
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:  # O(1) ルックアップ
            return [seen[complement], i]
        seen[num] = i
 
# パターン2: ソートして二分探索
# 問題: ソート済み配列で target 以上の最小値を見つける
 
# ❌ O(n): 線形探索
def find_ceiling_linear(arr, target):
    for x in arr:
        if x >= target:
            return x
 
# ✅ O(log n): 二分探索
import bisect
def find_ceiling_binary(arr, target):
    idx = bisect.bisect_left(arr, target)
    return arr[idx] if idx < len(arr) else None
 
# パターン3: スライディングウィンドウ
# 問題: 長さ k の連続部分配列の最大合計
 
# ❌ O(nk): 毎回合計を計算
def max_sum_brute(arr, k):
    max_sum = 0
    for i in range(len(arr) - k + 1):
        max_sum = max(max_sum, sum(arr[i:i+k]))
    return max_sum
 
# ✅ O(n): ウィンドウをスライド
def max_sum_sliding(arr, k):
    window = sum(arr[:k])
    max_sum = window
    for i in range(k, len(arr)):
        window += arr[i] - arr[i-k]  # 追加と削除
        max_sum = max(max_sum, window)
    return max_sum

# パターン4: 前計算（Prefix Sum）
# 問題: 区間 [l, r] の合計をQ回クエリされる
 
# ❌ O(n × Q): 毎回合計を計算
def range_sum_brute(arr, queries):
    results = []
    for l, r in queries:
        results.append(sum(arr[l:r+1]))  # O(n)
    return results
 
# ✅ O(n + Q): 前計算で O(1) クエリ
def range_sum_prefix(arr, queries):
    n = len(arr)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + arr[i]  # 前計算 O(n)
 
    results = []
    for l, r in queries:
        results.append(prefix[r+1] - prefix[l])  # O(1)
    return results
 
# パターン5: 二ポインタ
# 問題: ソート済み配列で条件を満たすペアを見つける
 
# ❌ O(n²): 全ペア
def count_pairs_brute(arr, target):
    count = 0
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            if arr[i] + arr[j] <= target:
                count += 1
    return count
 
# ✅ O(n): 二ポインタ（ソート済み前提）
def count_pairs_two_pointer(arr, target):
    count = 0
    left, right = 0, len(arr) - 1
    while left < right:
        if arr[left] + arr[right] <= target:
            count += right - left  # left と left+1...right の全ペア
            left += 1
        else:
            right -= 1
    return count
 
# パターン6: 累積最大値/最小値の前計算
# 問題: 株式売買の最大利益
 
# ❌ O(n²): 全ペアの売買を比較
def max_profit_brute(prices):
    max_p = 0
    for i in range(len(prices)):
        for j in range(i+1, len(prices)):
            max_p = max(max_p, prices[j] - prices[i])
    return max_p
 
# ✅ O(n): 最小値を追跡しながら走査
def max_profit_optimal(prices):
    min_price = float('inf')
    max_profit = 0
    for price in prices:
        min_price = min(min_price, price)
        max_profit = max(max_profit, price - min_price)
    return max_profit
 
# パターン7: 単調スタック
# 問題: 各要素の「右側で最初に大きい要素」を求める
 
# ❌ O(n²): 各要素から右方向に線形探索
def next_greater_brute(arr):
    n = len(arr)
    result = [-1] * n
    for i in range(n):
        for j in range(i+1, n):
            if arr[j] > arr[i]:
                result[i] = arr[j]
                break
    return result
 
# ✅ O(n): 単調スタック
def next_greater_stack(arr):
    n = len(arr)
    result = [-1] * n
    stack = []  # インデックスのスタック
    for i in range(n):
        while stack and arr[i] > arr[stack[-1]]:
            result[stack.pop()] = arr[i]
        stack.append(i)
    return result
# スタックへのpush/popは各要素1回ずつ → O(n)

# デバッグ用ユーティリティ
import logging
import traceback
from functools import wraps
 
# ロガーの設定
logging.basicConfig(
    level=logging.DEBUG,
    format='%(asctime)s [%(levelname)s] %(name)s: %(message)s'
)
logger = logging.getLogger(__name__)
 
def debug_decorator(func):
    """関数の入出力をログ出力するデコレータ"""
    @wraps(func)
    def wrapper(*args, **kwargs):
        logger.debug(f"呼び出し: {func.__name__}(args={args}, kwargs={kwargs})")
        try:
            result = func(*args, **kwargs)
            logger.debug(f"戻り値: {func.__name__} -> {result}")
            return result
        except Exception as e:
            logger.error(f"例外発生: {func.__name__}: {e}")
            logger.error(traceback.format_exc())
            raise
    return wrapper
 
@debug_decorator
def process_data(items):
    """データ処理（デバッグ対象）"""
    if not items:
        raise ValueError("空のデータ")
    return [item * 2 for item in items]

# 設計判断の記録テンプレート
class ArchitectureDecisionRecord:
    """ADR (Architecture Decision Record) の作成"""
 
    def __init__(self, title: str):
        self.title = title
        self.context = ""
        self.decision = ""
        self.consequences = []
        self.alternatives = []
 
    def set_context(self, context: str):
        """背景と課題の記述"""
        self.context = context
        return self
 
    def set_decision(self, decision: str):
        """決定内容の記述"""
        self.decision = decision
        return self
 
    def add_consequence(self, consequence: str, positive: bool = True):
        """結果の追加"""
        self.consequences.append({
            'description': consequence,
            'type': 'positive' if positive else 'negative'
        })
        return self
 
    def add_alternative(self, name: str, reason_rejected: str):
        """却下した代替案の追加"""
        self.alternatives.append({
            'name': name,
            'reason_rejected': reason_rejected
        })
        return self
 
    def to_markdown(self) -> str:
        """Markdown形式で出力"""
        md = f"# ADR: {self.title}\n\n"
        md += f"## 背景\n{self.context}\n\n"
        md += f"## 決定\n{self.decision}\n\n"
        md += "## 結果\n"
        for c in self.consequences:
            icon = "✅" if c['type'] == 'positive' else "⚠️"
            md += f"- {icon} {c['description']}\n"
        md += "\n## 却下した代替案\n"
        for a in self.alternatives:
            md += f"- **{a['name']}**: {a['reason_rejected']}\n"
        return md

# セキュアコーディング例
import hashlib
import secrets
import hmac
from typing import Optional
 
class SecurityUtils:
    """セキュリティユーティリティ"""
 
    @staticmethod
    def generate_token(length: int = 32) -> str:
        """暗号学的に安全なトークン生成"""
        return secrets.token_urlsafe(length)
 
    @staticmethod
    def hash_password(password: str, salt: Optional[str] = None) -> tuple:
        """パスワードのハッシュ化"""
        if salt is None:
            salt = secrets.token_hex(16)
        hashed = hashlib.pbkdf2_hmac(
            'sha256',
            password.encode('utf-8'),
            salt.encode('utf-8'),
            iterations=100000
        )
        return hashed.hex(), salt
 
    @staticmethod
    def verify_password(password: str, hashed: str, salt: str) -> bool:
        """パスワードの検証"""
        new_hash, _ = SecurityUtils.hash_password(password, salt)
        return hmac.compare_digest(new_hash, hashed)
 
    @staticmethod
    def sanitize_input(value: str) -> str:
        """入力値のサニタイズ"""
        dangerous_chars = ['<', '>', '"', "'", '&', '\\']
        result = value
        for char in dangerous_chars:
            result = result.replace(char, '')
        return result.strip()
 
# 使用例
token = SecurityUtils.generate_token()
hashed, salt = SecurityUtils.hash_password("my_password")
is_valid = SecurityUtils.verify_password("my_password", hashed, salt)

# マイグレーションスクリプトのテンプレート
import json
import logging
from pathlib import Path
from datetime import datetime
from typing import List, Dict, Callable
 
logger = logging.getLogger(__name__)
 
class MigrationRunner:
    """段階的マイグレーション実行エンジン"""
 
    def __init__(self, migration_dir: str):
        self.migration_dir = Path(migration_dir)
        self.migrations: List[Dict] = []
        self.completed: List[str] = []
 
    def register(self, version: str, description: str,
                 up: Callable, down: Callable):
        """マイグレーションの登録"""
        self.migrations.append({
            'version': version,
            'description': description,
            'up': up,
            'down': down,
            'registered_at': datetime.now().isoformat()
        })
 
    def run_up(self, target_version: str = None):
        """マイグレーションの実行（アップグレード）"""
        for migration in self.migrations:
            if migration['version'] in self.completed:
                continue
            logger.info(f"実行中: {migration['version']} - "
                       f"{migration['description']}")
            try:
                migration['up']()
                self.completed.append(migration['version'])
                logger.info(f"完了: {migration['version']}")
            except Exception as e:
                logger.error(f"失敗: {migration['version']}: {e}")
                raise
            if target_version and migration['version'] == target_version:
                break
 
    def run_down(self, target_version: str):
        """マイグレーションのロールバック"""
        for migration in reversed(self.migrations):
            if migration['version'] not in self.completed:
                continue
            if migration['version'] == target_version:
                break
            logger.info(f"ロールバック: {migration['version']}")
            migration['down']()
            self.completed.remove(migration['version'])
 
    def status(self) -> Dict:
        """マイグレーション状態の確認"""
        return {
            'total': len(self.migrations),
            'completed': len(self.completed),
            'pending': len(self.migrations) - len(self.completed),
            'versions': {
                m['version']: 'completed'
                if m['version'] in self.completed else 'pending'
                for m in self.migrations
            }
        }