/* cache_benchmark.c - 配列 vs 連結リストの走査速度比較 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define N 10000000
 
typedef struct Node {
    int value;
    struct Node *next;
} Node;
 
int main(void) {
    /* --- 配列の走査 --- */
    int *arr = malloc(sizeof(int) * N);
    for (int i = 0; i < N; i++) arr[i] = i;
 
    clock_t start = clock();
    long long sum_arr = 0;
    for (int i = 0; i < N; i++) {
        sum_arr += arr[i];
    }
    clock_t end = clock();
    double time_arr = (double)(end - start) / CLOCKS_PER_SEC;
 
    /* --- 連結リストの走査 --- */
    Node *head = NULL;
    for (int i = N - 1; i >= 0; i--) {
        Node *node = malloc(sizeof(Node));
        node->value = i;
        node->next = head;
        head = node;
    }
 
    start = clock();
    long long sum_list = 0;
    Node *cur = head;
    while (cur) {
        sum_list += cur->value;
        cur = cur->next;
    }
    end = clock();
    double time_list = (double)(end - start) / CLOCKS_PER_SEC;
 
    printf("配列走査     : %.4f 秒 (sum = %lld)\n", time_arr, sum_arr);
    printf("連結リスト走査: %.4f 秒 (sum = %lld)\n", time_list, sum_list);
    printf("比率         : %.1fx\n", time_list / time_arr);
 
    /* メモリ解放 */
    free(arr);
    while (head) {
        Node *tmp = head;
        head = head->next;
        free(tmp);
    }
    return 0;
}

/* row_vs_col.c - 行優先走査 vs 列優先走査の速度比較 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define ROWS 4096
#define COLS 4096
 
int main(void) {
    int (*matrix)[COLS] = malloc(sizeof(int[ROWS][COLS]));
 
    /* 初期化 */
    for (int i = 0; i < ROWS; i++)
        for (int j = 0; j < COLS; j++)
            matrix[i][j] = i + j;
 
    /* 行優先走査 (キャッシュフレンドリー) */
    clock_t start = clock();
    long long sum1 = 0;
    for (int i = 0; i < ROWS; i++)
        for (int j = 0; j < COLS; j++)
            sum1 += matrix[i][j];
    clock_t end = clock();
    double time_row = (double)(end - start) / CLOCKS_PER_SEC;
 
    /* 列優先走査 (キャッシュ非フレンドリー) */
    start = clock();
    long long sum2 = 0;
    for (int j = 0; j < COLS; j++)
        for (int i = 0; i < ROWS; i++)
            sum2 += matrix[i][j];
    end = clock();
    double time_col = (double)(end - start) / CLOCKS_PER_SEC;
 
    printf("行優先走査: %.4f 秒 (sum = %lld)\n", time_row, sum1);
    printf("列優先走査: %.4f 秒 (sum = %lld)\n", time_col, sum2);
    printf("比率      : %.1fx\n", time_col / time_row);
 
    free(matrix);
    return 0;
}

import numpy as np
 
# C order (行優先, デフォルト)
a = np.array([[1, 2, 3], [4, 5, 6]], order='C')
print(a.strides)  # (24, 8) — 行を1つ進むには24バイト、列は8バイト
 
# Fortran order (列優先)
b = np.array([[1, 2, 3], [4, 5, 6]], order='F')
print(b.strides)  # (8, 16) — 行を1つ進むには8バイト、列は16バイト
 
# パフォーマンスの違い
import timeit
 
n = 2000
c_arr = np.random.rand(n, n)               # C order
f_arr = np.asfortranarray(np.random.rand(n, n))  # Fortran order
 
# 行方向の合計 (C order が有利)
t1 = timeit.timeit(lambda: c_arr.sum(axis=1), number=100)
t2 = timeit.timeit(lambda: f_arr.sum(axis=1), number=100)
print(f"行合計: C order={t1:.4f}s, F order={t2:.4f}s")
 
# 列方向の合計 (Fortran order が有利)
t3 = timeit.timeit(lambda: c_arr.sum(axis=0), number=100)
t4 = timeit.timeit(lambda: f_arr.sum(axis=0), number=100)
print(f"列合計: C order={t3:.4f}s, F order={t4:.4f}s")

# CPython list の内部構造を観察する
import sys
 
lst = []
prev_size = sys.getsizeof(lst)
print(f"{'len':>4s}  {'sizeof':>8s}  {'capacity推定':>12s}  {'リサイズ':>8s}")
print("-" * 50)
 
for i in range(65):
    lst.append(i)
    current_size = sys.getsizeof(lst)
    # ポインタサイズ (64bit) = 8バイト
    # オーバーヘッド = 空listのサイズ
    overhead = sys.getsizeof([])
    capacity = (current_size - overhead) // 8
    resized = "◆" if current_size != prev_size else ""
    if resized or i < 10 or i % 10 == 0:
        print(f"{len(lst):4d}  {current_size:8d}  {capacity:12d}  {resized:>8s}")
    prev_size = current_size
 
# CPython の成長パターン (cpython/Objects/listobject.c より):
# new_allocated = new_size + (new_size >> 3) + (6 if new_size < 9 else 3)
# つまり: new_allocated = new_size + new_size/8 + 定数
# 成長率は約 12.5% ずつ増加 (= 成長因子 ~1.125)

# アンチパターン: ループ内での文字列連結 — O(n^2)
def build_string_bad(n):
    result = ""
    for i in range(n):
        result += str(i) + ","  # 毎回新しい文字列を生成
    return result
 
# 正しいパターン: join を使う — O(n)
def build_string_good(n):
    parts = [str(i) for i in range(n)]
    return ",".join(parts)
 
# ベンチマーク
import timeit
n = 50000
t1 = timeit.timeit(lambda: build_string_bad(n), number=5)
t2 = timeit.timeit(lambda: build_string_good(n), number=5)
print(f"連結 (+= ):  {t1:.3f}s")
print(f"join:        {t2:.3f}s")
print(f"比率:        {t1/t2:.1f}x")
# 典型的な結果: join は += の10倍以上高速 (n=50000)

# CPython の文字列インターニング
a = "hello"
b = "hello"
print(a is b)       # True — 同じオブジェクトを共有
 
# コンパイル時にインターン化される条件 (CPython):
# - 識別子として有効な文字列 (英数字とアンダースコアのみ)
# - 長さが一定以下
 
c = "hello world"
d = "hello world"
print(c is d)       # True (CPython 3.x ではコンパイル時定数はインターン化)
 
# 実行時に動的生成された文字列は通常インターン化されない
e = "hello" + " " + "world"
f = "hello" + " " + "world"
# CPython の最適化レベルによって結果が異なる
 
# 明示的なインターニング
import sys
g = sys.intern("hello world 123")
h = sys.intern("hello world 123")
print(g is h)       # True — 常に同じオブジェクト
 
# Java の場合:
# String s1 = "hello";    // リテラルプールから取得
# String s2 = "hello";    // 同じ参照
# s1 == s2                // true (参照比較)
# new String("hello").intern() == s1  // true

def naive_search(text: str, pattern: str) -> list[int]:
    """素朴な文字列探索 — O(nm)"""
    n, m = len(text), len(pattern)
    positions = []
    for i in range(n - m + 1):
        if text[i:i+m] == pattern:
            positions.append(i)
    return positions
 
# テスト
text = "AABAACAADAABAABA"
pattern = "AABA"
print(naive_search(text, pattern))  # [0, 9, 12]

def kmp_search(text: str, pattern: str) -> list[int]:
    """KMP アルゴリズム — O(n + m)"""
    n, m = len(text), len(pattern)
    if m == 0:
        return []
 
    # 失敗関数 (failure function) の構築 — O(m)
    # fail[i] = pattern[0:i+1] の真の接頭辞と接尾辞の最長一致長
    fail = [0] * m
    j = 0
    for i in range(1, m):
        while j > 0 and pattern[i] != pattern[j]:
            j = fail[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        fail[i] = j
 
    # 探索 — O(n)
    positions = []
    j = 0
    for i in range(n):
        while j > 0 and text[i] != pattern[j]:
            j = fail[j - 1]
        if text[i] == pattern[j]:
            j += 1
        if j == m:
            positions.append(i - m + 1)
            j = fail[j - 1]
 
    return positions
 
# テスト
text = "AABAACAADAABAABA"
pattern = "AABA"
print(kmp_search(text, pattern))  # [0, 9, 12]
 
# 失敗関数の動作例:
# pattern = "AABA"
# fail = [0, 1, 0, 1]
#
# A  A  B  A
# 0  1  0  1
# ↑  ↑  ↑  ↑
# 無  A  無  A   ← 接頭辞=接尾辞の最長一致

def rabin_karp_search(text: str, pattern: str, base: int = 256,
                      mod: int = 101) -> list[int]:
    """Rabin-Karp アルゴリズム — 平均 O(n + m)"""
    n, m = len(text), len(pattern)
    if m > n:
        return []
 
    positions = []
 
    # パターンのハッシュ値を計算
    p_hash = 0
    t_hash = 0
    h = pow(base, m - 1, mod)  # base^(m-1) mod mod
 
    for i in range(m):
        p_hash = (p_hash * base + ord(pattern[i])) % mod
        t_hash = (t_hash * base + ord(text[i])) % mod
 
    # スライドしながら比較
    for i in range(n - m + 1):
        if p_hash == t_hash:
            # ハッシュ一致 → 実際に比較 (偽陽性を排除)
            if text[i:i+m] == pattern:
                positions.append(i)
 
        # ローリングハッシュの更新
        if i < n - m:
            t_hash = (t_hash - ord(text[i]) * h) * base + ord(text[i + m])
            t_hash %= mod
 
    return positions
 
# テスト
text = "AABAACAADAABAABA"
pattern = "AABA"
print(rabin_karp_search(text, pattern))  # [0, 9, 12]

def boyer_moore_search(text: str, pattern: str) -> list[int]:
    """Boyer-Moore (Bad Character ルールのみ) — 実用的に O(n/m)"""
    n, m = len(text), len(pattern)
    if m == 0 or m > n:
        return []
 
    # Bad Character テーブル: 各文字がパターン中で最後に出現する位置
    bad_char = {}
    for i in range(m):
        bad_char[pattern[i]] = i
 
    positions = []
    s = 0  # テキスト上のシフト量
    while s <= n - m:
        j = m - 1  # パターン末尾から比較
 
        while j >= 0 and pattern[j] == text[s + j]:
            j -= 1
 
        if j < 0:
            # 完全一致
            positions.append(s)
            s += 1  # Good Suffix ルールがあればもっとスキップ可能
        else:
            # 不一致
            char = text[s + j]
            skip = j - bad_char.get(char, -1)
            s += max(1, skip)
 
    return positions
 
# テスト
text = "AABAACAADAABAABA"
pattern = "AABA"
print(boyer_moore_search(text, pattern))  # [0, 9, 12]

def binary_search(arr: list[int], target: int) -> int:
    """二分探索 — O(log n)
    見つかった場合はインデックスを、見つからない場合は -1 を返す
    """
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2  # オーバーフロー防止
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1
 
# lower_bound: target 以上の最小のインデックス
def lower_bound(arr: list[int], target: int) -> int:
    """C++ std::lower_bound 相当 — O(log n)"""
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo
 
# upper_bound: target より大きい最小のインデックス
def upper_bound(arr: list[int], target: int) -> int:
    """C++ std::upper_bound 相当 — O(log n)"""
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] <= target:
            lo = mid + 1
        else:
            hi = mid
    return lo
 
# テスト
arr = [1, 3, 3, 3, 5, 7, 9]
print(binary_search(arr, 3))    # 2 (最初に見つかったもの)
print(lower_bound(arr, 3))      # 1 (3以上の最小インデックス)
print(upper_bound(arr, 3))      # 4 (3より大きい最小インデックス)
print(lower_bound(arr, 4))      # 4 (4以上の最小 → arr[4]=5)

def two_sum_sorted(arr: list[int], target: int) -> tuple[int, int] | None:
    """ソート済み配列で合計が target になるペアを探す — O(n)"""
    left, right = 0, len(arr) - 1
    while left < right:
        s = arr[left] + arr[right]
        if s == target:
            return (left, right)
        elif s < target:
            left += 1
        else:
            right -= 1
    return None
 
# テスト
arr = [1, 2, 4, 6, 8, 10]
print(two_sum_sorted(arr, 10))  # (1, 4) → arr[1]+arr[4] = 2+8 = 10
 
# 応用: 3Sum (合計が 0 になる3つ組を列挙)
def three_sum(arr: list[int]) -> list[tuple[int, int, int]]:
    """3つの要素の合計が0になる組み合わせを列挙 — O(n^2)"""
    arr.sort()
    n = len(arr)
    result = []
    for i in range(n - 2):
        if i > 0 and arr[i] == arr[i - 1]:
            continue  # 重複スキップ
        left, right = i + 1, n - 1
        while left < right:
            s = arr[i] + arr[left] + arr[right]
            if s == 0:
                result.append((arr[i], arr[left], arr[right]))
                while left < right and arr[left] == arr[left + 1]:
                    left += 1  # 重複スキップ
                while left < right and arr[right] == arr[right - 1]:
                    right -= 1  # 重複スキップ
                left += 1
                right -= 1
            elif s < 0:
                left += 1
            else:
                right -= 1
    return result
 
print(three_sum([-1, 0, 1, 2, -1, -4]))
# [(-1, -1, 2), (-1, 0, 1)]

# 固定長ウィンドウ: 長さ k の連続部分配列の最大合計
def max_sum_subarray(arr: list[int], k: int) -> int:
    """固定長スライディングウィンドウ — O(n)"""
    n = len(arr)
    if n < k:
        return 0
    window_sum = sum(arr[:k])
    best = window_sum
    for i in range(k, n):
        window_sum += arr[i] - arr[i - k]
        best = max(best, window_sum)
    return best
 
print(max_sum_subarray([1, 4, 2, 10, 2, 3, 1, 0, 20], 4))  # 24
 
# 可変長ウィンドウ: 合計が target 以上の最短部分配列
def min_subarray_len(arr: list[int], target: int) -> int:
    """可変長スライディングウィンドウ — O(n)"""
    n = len(arr)
    left = 0
    current_sum = 0
    min_len = float('inf')
    for right in range(n):
        current_sum += arr[right]
        while current_sum >= target:
            min_len = min(min_len, right - left + 1)
            current_sum -= arr[left]
            left += 1
    return min_len if min_len != float('inf') else 0
 
print(min_subarray_len([2, 3, 1, 2, 4, 3], 7))  # 2 (部分配列 [4, 3])
 
# 可変長ウィンドウ: 重複なしの最長部分文字列
def longest_unique_substring(s: str) -> int:
    """重複なしの最長部分文字列の長さ — O(n)"""
    seen = {}
    left = 0
    max_len = 0
    for right, char in enumerate(s):
        if char in seen and seen[char] >= left:
            left = seen[char] + 1
        seen[char] = right
        max_len = max(max_len, right - left + 1)
    return max_len
 
print(longest_unique_substring("abcabcbb"))  # 3 ("abc")
print(longest_unique_substring("pwwkew"))    # 3 ("wke")

class PrefixSum:
    """プレフィックス和 — 構築 O(n), クエリ O(1)"""
 
    def __init__(self, arr: list[int]):
        n = len(arr)
        self.prefix = [0] * (n + 1)
        for i in range(n):
            self.prefix[i + 1] = self.prefix[i] + arr[i]
 
    def range_sum(self, left: int, right: int) -> int:
        """arr[left:right+1] の合計を O(1) で返す"""
        return self.prefix[right + 1] - self.prefix[left]
 
# テスト
arr = [3, 1, 4, 1, 5, 9, 2, 6]
ps = PrefixSum(arr)
print(ps.range_sum(2, 5))  # arr[2]+arr[3]+arr[4]+arr[5] = 4+1+5+9 = 19
print(ps.range_sum(0, 7))  # 全体の合計 = 31
 
# 2次元プレフィックス和
class PrefixSum2D:
    """2次元プレフィックス和 — 構築 O(nm), クエリ O(1)"""
 
    def __init__(self, matrix: list[list[int]]):
        if not matrix:
            self.prefix = [[]]
            return
        rows, cols = len(matrix), len(matrix[0])
        self.prefix = [[0] * (cols + 1) for _ in range(rows + 1)]
        for i in range(rows):
            for j in range(cols):
                self.prefix[i+1][j+1] = (matrix[i][j]
                    + self.prefix[i][j+1]
                    + self.prefix[i+1][j]
                    - self.prefix[i][j])
 
    def range_sum(self, r1: int, c1: int, r2: int, c2: int) -> int:
        """matrix[r1:r2+1][c1:c2+1] の合計を O(1) で返す"""
        return (self.prefix[r2+1][c2+1]
                - self.prefix[r1][c2+1]
                - self.prefix[r2+1][c1]
                + self.prefix[r1][c1])
 
# テスト
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
ps2d = PrefixSum2D(matrix)
print(ps2d.range_sum(0, 0, 1, 1))  # 1+2+4+5 = 12
print(ps2d.range_sum(1, 1, 2, 2))  # 5+6+8+9 = 28

import numpy as np
import timeit
 
n = 10_000_000
 
# Python list での合計
py_list = list(range(n))
t1 = timeit.timeit(lambda: sum(py_list), number=10)
 
# NumPy array での合計 (SIMD活用)
np_arr = np.arange(n, dtype=np.int64)
t2 = timeit.timeit(lambda: np_arr.sum(), number=10)
 
print(f"Python sum : {t1:.4f}s")
print(f"NumPy sum  : {t2:.4f}s")
print(f"速度比     : {t1/t2:.0f}x")
# 典型的な結果: NumPy は Python の 50-100 倍高速

# NG: O(n^2) — 毎回文字列全体をコピー
def build_csv_bad(rows: list[list[str]]) -> str:
    result = ""
    for row in rows:
        result += ",".join(row) + "\n"  # 毎回新しい文字列を生成
    return result
 
# OK: O(n) — リストに貯めて最後に結合
def build_csv_good(rows: list[list[str]]) -> str:
    lines = []
    for row in rows:
        lines.append(",".join(row))
    return "\n".join(lines)
 
# さらに良い: ジェネレータ式
def build_csv_best(rows: list[list[str]]) -> str:
    return "\n".join(",".join(row) for row in rows)

// NG: O(n^2)
String result = "";
for (String s : list) {
    result += s;  // 毎回新しい String オブジェクト生成
}
 
// OK: O(n)
StringBuilder sb = new StringBuilder();
for (String s : list) {
    sb.append(s);
}
String result = sb.toString();

# NG: O(n^2) — 毎回全要素をシフト
def build_reversed_bad(items: list) -> list:
    result = []
    for item in items:
        result.insert(0, item)  # O(n) × n回 = O(n^2)
    return result
 
# OK: O(n) — 末尾に追加して反転
def build_reversed_good(items: list) -> list:
    result = []
    for item in items:
        result.append(item)  # O(1) 償却
    result.reverse()  # O(n) — 1回だけ
    return result
 
# さらに良い: collections.deque を使う
from collections import deque
def build_reversed_deque(items: list) -> deque:
    result = deque()
    for item in items:
        result.appendleft(item)  # O(1)
    return result
 
# ベンチマーク
import timeit
n = 50000
items = list(range(n))
t1 = timeit.timeit(lambda: build_reversed_bad(items), number=5)
t2 = timeit.timeit(lambda: build_reversed_good(items), number=5)
t3 = timeit.timeit(lambda: build_reversed_deque(items), number=5)
print(f"insert(0,x): {t1:.3f}s")
print(f"append+rev : {t2:.3f}s")
print(f"deque      : {t3:.3f}s")

# NG: スライスは新しいリストを生成する（意図しないコピー）
def process_subarray_bad(arr: list, start: int, end: int) -> int:
    sub = arr[start:end]  # O(end-start) のコピーが発生
    return sum(sub)
 
# OK: インデックスで範囲を指定して処理
def process_subarray_good(arr: list, start: int, end: int) -> int:
    total = 0
    for i in range(start, end):
        total += arr[i]  # コピーなし
    return total
 
# NumPy の場合: ビュー vs コピー
import numpy as np
arr = np.array([1, 2, 3, 4, 5])
 
view = arr[1:4]      # ビュー（コピーなし、元配列と共有）
view[0] = 99         # arr も変更される！
print(arr)            # [1, 99, 3, 4, 5]
 
copy = arr[1:4].copy()  # 明示的なコピー
copy[0] = 0           # arr は変更されない
print(arr)            # [1, 99, 3, 4, 5]

def find_max_bad(arr: list[int]) -> int:
    """NG: 空配列で例外"""
    max_val = arr[0]  # IndexError if arr is empty!
    for x in arr[1:]:
        max_val = max(max_val, x)
    return max_val
 
def find_max_good(arr: list[int]) -> int | None:
    """OK: 空配列を適切に処理"""
    if not arr:
        return None
    max_val = arr[0]
    for x in arr[1:]:
        max_val = max(max_val, x)
    return max_val
 
# テスト
print(find_max_good([]))         # None
print(find_max_good([42]))       # 42
print(find_max_good([3, 1, 4]))  # 4
 
# 二分探索でのエッジケース
def binary_search_safe(arr: list[int], target: int) -> int:
    """空配列でも安全な二分探索"""
    if not arr:
        return -1
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1
 
# 回文判定のエッジケース
def is_palindrome(s: str) -> bool:
    """空文字列と1文字は回文"""
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True  # 空文字列と1文字は True
 
assert is_palindrome("") == True
assert is_palindrome("a") == True
assert is_palindrome("ab") == False
assert is_palindrome("aba") == True

/* C言語での二分探索のオーバーフロー問題 */
 
/* NG: lo + hi がオーバーフローする可能性 */
int mid_bad = (lo + hi) / 2;
/* lo = 2,000,000,000, hi = 2,000,000,000 の場合
   lo + hi = 4,000,000,000 > INT_MAX (2,147,483,647)
   → 負の値になり、不正なインデックスに */
 
/* OK: オーバーフローしない計算 */
int mid_good = lo + (hi - lo) / 2;
/* hi - lo は常に非負で、lo + (hi-lo)/2 は lo 以上 hi 以下 */
 
/* Java でも同じ問題が存在する:
   java.util.Arrays.binarySearch() は
   JDK 6 で (lo + hi) >>> 1 に修正された
   (符号なし右シフトでオーバーフローを回避) */

# Python は任意精度整数のためオーバーフローは発生しないが、
# 配列の合計がメモリを圧迫する場合がある
 
# 巨大な配列の合計
import sys
huge_list = [10**100] * 1000000
total = sum(huge_list)
# Python の int は任意精度なのでオーバーフローしないが、
# 各要素がPyObjectとして巨大なメモリを消費する
 
# NumPy の場合はオーバーフローする
import numpy as np
arr = np.array([2**62, 2**62], dtype=np.int64)
print(arr.sum())  # オーバーフロー! → 負の値になる
# 対策: dtype=np.int128 は存在しないため、Python の int に変換
print(sum(int(x) for x in arr))  # 正しい結果

# 「文字数」は何を意味するかに依存する
 
text = "👨‍👩‍👧‍👦"  # 家族の絵文字
 
# バイト数 (UTF-8)
print(len(text.encode('utf-8')))    # 25
 
# コードポイント数
print(len(text))                     # 7 (Python は Unicode コードポイント単位)
 
# 書記素クラスタ (grapheme cluster) 数 — 人間が認識する「文字」の数
# 標準ライブラリだけでは取得困難。
# pip install grapheme
# import grapheme
# print(grapheme.length(text))       # 1
 
# 日本語の例
text_ja = "が"  # U+304C (が) — 1コードポイント
text_ja2 = "が"  # U+304B (か) + U+3099 (濁点) — 2コードポイント
# 見た目は同じだが len() が異なる場合がある
 
# 正規化
import unicodedata
nfc = unicodedata.normalize('NFC', text_ja2)   # 合成形: 1コードポイント
nfd = unicodedata.normalize('NFD', text_ja)    # 分解形: 2コードポイント
print(len(nfc), len(nfd))  # 1, 2
 
# 安全な文字列比較: 正規化してから比較
def safe_compare(s1: str, s2: str) -> bool:
    return unicodedata.normalize('NFC', s1) == unicodedata.normalize('NFC', s2)

def rotate_array(arr: list, k: int) -> None:
    """配列をインプレースで k 個分右に回転 — O(n) 時間, O(1) 空間"""
    n = len(arr)
    if n == 0:
        return
    k = k % n  # k が n より大きい場合に対応
 
    def reverse(start: int, end: int) -> None:
        while start < end:
            arr[start], arr[end] = arr[end], arr[start]
            start += 1
            end -= 1
 
    # Step 1: 全体を反転   [1,2,3,4,5,6,7] → [7,6,5,4,3,2,1]
    reverse(0, n - 1)
    # Step 2: 前半を反転   [7,6,5,4,3,2,1] → [5,6,7,4,3,2,1]
    reverse(0, k - 1)
    # Step 3: 後半を反転   [5,6,7,4,3,2,1] → [5,6,7,1,2,3,4]
    reverse(k, n - 1)
 
# テスト
arr = [1, 2, 3, 4, 5, 6, 7]
rotate_array(arr, 3)
print(arr)  # [5, 6, 7, 1, 2, 3, 4]

def is_palindrome_alnum(s: str) -> bool:
    """英数字のみで回文判定 — O(n) 時間, O(1) 空間"""
    left, right = 0, len(s) - 1
    while left < right:
        # 英数字以外をスキップ
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True
 
# テスト
print(is_palindrome_alnum("A man, a plan, a canal: Panama"))  # True
print(is_palindrome_alnum("race a car"))                       # False
print(is_palindrome_alnum(""))                                 # True

def longest_palindrome_substring(s: str) -> str:
    """最長回文部分文字列 — O(n^2) 時間, O(1) 空間
    (Manacher のアルゴリズムで O(n) も可能)
    """
    if not s:
        return ""
 
    start, max_len = 0, 1
 
    def expand_around_center(left: int, right: int) -> tuple[int, int]:
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - left - 1
 
    for i in range(len(s)):
        # 奇数長の回文
        l1, len1 = expand_around_center(i, i)
        if len1 > max_len:
            start, max_len = l1, len1
 
        # 偶数長の回文
        if i + 1 < len(s):
            l2, len2 = expand_around_center(i, i + 1)
            if len2 > max_len:
                start, max_len = l2, len2
 
    return s[start:start + max_len]
 
# テスト
print(longest_palindrome_substring("babad"))     # "bab" or "aba"
print(longest_palindrome_substring("cbbd"))      # "bb"
print(longest_palindrome_substring("racecar"))   # "racecar"

def rotate_matrix(matrix: list[list[int]]) -> None:
    """n×n 行列を時計回りに90度回転 — O(n^2) 時間, O(1) 空間"""
    n = len(matrix)
 
    # Step 1: 転置 (行と列を入れ替え)
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
 
    # Step 2: 各行を反転
    for i in range(n):
        matrix[i].reverse()
 
# テスト
matrix = [
    [1,  2,  3,  4],
    [5,  6,  7,  8],
    [9,  10, 11, 12],
    [13, 14, 15, 16]
]
rotate_matrix(matrix)
for row in matrix:
    print(row)
# [13, 9,  5, 1]
# [14, 10, 6, 2]
# [15, 11, 7, 3]
# [16, 12, 8, 4]

def spiral_order(matrix: list[list[int]]) -> list[int]:
    """スパイラル順で行列要素を返す — O(mn) 時間"""
    if not matrix or not matrix[0]:
        return []
 
    result = []
    top, bottom = 0, len(matrix) - 1
    left, right = 0, len(matrix[0]) - 1
 
    while top <= bottom and left <= right:
        # 上の行: 左→右
        for j in range(left, right + 1):
            result.append(matrix[top][j])
        top += 1
 
        # 右の列: 上→下
        for i in range(top, bottom + 1):
            result.append(matrix[i][right])
        right -= 1
 
        # 下の行: 右→左
        if top <= bottom:
            for j in range(right, left - 1, -1):
                result.append(matrix[bottom][j])
            bottom -= 1
 
        # 左の列: 下→上
        if left <= right:
            for i in range(bottom, top - 1, -1):
                result.append(matrix[i][left])
            left += 1
 
    return result
 
# テスト
matrix = [
    [1,  2,  3,  4],
    [5,  6,  7,  8],
    [9,  10, 11, 12]
]
print(spiral_order(matrix))
# [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]

from collections import Counter
 
def min_window(s: str, t: str) -> str:
    """最小ウィンドウ部分文字列 — O(|s| + |t|)"""
    if not s or not t:
        return ""
 
    need = Counter(t)
    missing = len(t)  # まだ満たされていない文字数
    best_start, best_len = 0, float('inf')
    left = 0
 
    for right, char in enumerate(s):
        if need[char] > 0:
            missing -= 1
        need[char] -= 1
 
        # すべての文字が含まれたらウィンドウを縮小
        while missing == 0:
            window_len = right - left + 1
            if window_len < best_len:
                best_start, best_len = left, window_len
 
            need[s[left]] += 1
            if need[s[left]] > 0:
                missing += 1
            left += 1
 
    return "" if best_len == float('inf') else s[best_start:best_start + best_len]
 
# テスト
print(min_window("ADOBECODEBANC", "ABC"))  # "BANC"
print(min_window("a", "a"))                 # "a"
print(min_window("a", "aa"))                # "" (不可能)

import sys
print(sys.getsizeof([1, 2, 3]))   # 120 (余剰容量を含む)
print(sys.getsizeof((1, 2, 3)))   # 64  (必要最小限)

# 配列が適切: 英小文字の頻度カウント
def count_letters_array(s: str) -> list[int]:
    counts = [0] * 26
    for c in s:
        counts[ord(c) - ord('a')] += 1
    return counts
 
# 辞書が適切: 任意の文字の頻度カウント
from collections import Counter
def count_chars_dict(s: str) -> dict[str, int]:
    return Counter(s)

a = "hello"
b = "hello"
c = "hel" + "lo"
 
print(a == b)    # True  — 値が同じ
print(a is b)    # True  — CPython がインターン化（実装依存!）
 
# 動的に生成された文字列
d = "".join(["h", "e", "l", "l", "o"])
print(a == d)    # True  — 値が同じ
print(a is d)    # False — 異なるオブジェクト（インターン化されない場合）
 
# 重要: 'is' での文字列比較は実装依存のため、絶対に使ってはならない
# PyPy, Jython, IronPython では CPython と異なる結果になる