C++競プロ用ライブラリ

はじめに

　競プロ用のメモです。表記の目安として、O(1) は定数時間、O(log N) は木構造やヒープでよく出る対数、O(N) は線形、O(N log N) はソート系の典型をイメージするとよいかと思います。

入力・出力

INT / LL / STR / CHR / DBL

用途: 変数宣言と入力を同時に行う入力マクロ

計算量: 各変数あたり O(1) 入力処理。実体は cin ラッパーなので、通常の入力と同等。

// ===== スカラー入力 =====
INT(a, b, c);     // int a, b, c;
LL(x, y);         // long long x, y;
STR(s);           // string s;
CHR(c);           // char c;
DBL(d);           // double d;

// ===== ベクトル入力 =====
VEC(int, v, n);   // size n の vector<int> v
VEC(ll, w, n);    // size n の vector<long long> w

// ===== 2変数同時配列入力 =====
VEC2(int, a, b, n);
// a[i], b[i] を同時に入力

// ===== 3変数同時配列入力 =====
VEC3(int, a, b, c, n);
// a[i], b[i], c[i] を同時に入力

// ===== 2次元配列 =====
VV(int, g, h, w);
// h × w の vector<vector<int>> g

getline

用途: 空白を含む1行の文字列入力を受け取る

計算量: 行長を L とすると O(L)。文字列を丸ごと読むときの基本。

string s;
getline(cin, s);

文字列・数値の読み分け

用途: 1トークンずつ読む基本形

計算量: 入力サイズに比例して O(文字数)。空白区切りの入力で最もよく使う。

int a, b;
long long x;
string s;
char c;
double d;

cin >> a >> b;
cin >> x;
cin >> s;
cin >> c;
cin >> d;

注意: string は空白で切られる。文全体を読みたいときは getline を使う。

文字列

stoi / stoll / stod

用途: 文字列を数値に変換する

int n = stoi("123");
long long m = stoll("999999999999");
double d = stod("3.14159");

to_string

用途: 数値を文字列に変換する

計算量: O(桁数)。デバッグ出力やラベル生成で非常に便利。

string s1 = to_string(42);
string s2 = to_string(1000000000000LL);

substr / find / replace

用途: 部分文字列の切り出し・探索・置換

計算量: substr は O(長さ)、find は実装依存だが最悪 O(NM) を意識、replace は O(N) 近傍。文字列処理は定数倍が重いことがある。

string s = "competitive programming";
string t = s.substr(0, 10);        // "competitive"
size_t p = s.find("program");
if (p != string::npos) {
    s.replace(p, 8, "contest");
}

stringstream

用途: 文字列を空白区切りで分解・結合する

計算量: O(文字数)。パース処理に便利だが、速度は直読みより遅いことが多い。

stringstream ss;
ss << "10 20 30";
int a, b, c;
ss >> a >> b >> c;

vector・配列

push_back / emplace_back / pop_back

用途: vector の末尾に追加・末尾を削除

計算量: 末尾追加は償却 O(1)、pop_back は O(1)。最頻出の基本操作。

vector<int> v;
v.push_back(3);
v.emplace_back(5);
v.pop_back();

resize / assign / clear

用途: サイズ変更・初期化・全消去

計算量: resize は増減要素数に依存、assign は O(N)、clear は O(1) 近傍だが、要素破棄コストは型に依存。

vector<int> v;
v.resize(10);          // 要素数10
v.assign(5, 7);        // [7, 7, 7, 7, 7]
v.clear();             // 空にする

erase / remove idiom

用途: vector / string から要素を消す

計算量: 1回の erase は O(N)。条件削除は remove_if と組み合わせるのが定番。

vector<int> v = {1, 2, 3, 2, 4};
v.erase(v.begin() + 1);  // 2番目を削除

v.erase(
    remove(v.begin(), v.end(), 2),
    v.end()
);

注意: ループ中の erase は連鎖すると O(N^2) になりやすい。

sort / stable_sort / reverse

用途: 並べ替え・安定ソート・反転

計算量: sort は O(N log N)、stable_sort も O(N log N) だが定数倍は重め、reverse は O(N)。

sort(v.begin(), v.end());
sort(v.begin(), v.end(), greater<>());
stable_sort(v.begin(), v.end());
reverse(v.begin(), v.end());

lower_bound / upper_bound

用途: ソート済み配列で境界を探す

計算量: O(log N)。「二分探索を標準関数で書く」場面の最重要候補。

auto it1 = lower_bound(v.begin(), v.end(), x); // x以上の最初
auto it2 = upper_bound(v.begin(), v.end(), x); // xより大きい最初

int idx1 = it1 - v.begin();
int idx2 = it2 - v.begin();

注意: 未ソート配列に使ってはいけない。

next_permutation

用途: 順列全探索、辞書順で次の並びを生成する

計算量: 1回あたり O(N)。全列挙は N! なので、サイズには強く注意。

sort(v.begin(), v.end());
do {
    // v を1通り処理
} while (next_permutation(v.begin(), v.end()));

注意: 出力はboolで、一回実行するたびにvの中身が次の順列になる。

多次元 vector

用途: 2次元・3次元配列を定義する

計算量: 初期化は要素数に比例して O(HW) や O(XYZ)。 DPの土台として頻出。

vector<vector<int>> a(h, vector<int>(w, 0));
vector<vector<long long>> dp(n, vector<long long>(m, INF));
vector<vector<vector<int>>> g(x, vector<vector<int>>(y, vector<int>(z)));

set / map / unordered

set / multiset

用途: 昇順に保たれる集合・重複許容集合

概要: set は「重複なし・自動ソートされた集合」、 multiset は「重複あり・自動ソートされた集合」。内部的には平衡二分木（多くの場合 Red-Black Tree）で管理される。

計算量: 追加・削除・探索はすべて O(log N)。 vector のような線形探索 O(N) を避けたい場合に有効。

重要な性質: 要素は常にソート順で保持されるため、 lower_bound・upper_bound がそのまま使える。また「存在判定」「最小/最大取得」が高速。

set<int> st;

// insert: 要素追加
st.insert(10);
st.insert(5);

// find: 探索（なければ end()）
auto it = st.find(10);

// erase: 削除（値 or iterator）
st.erase(10);

// size: setの大きさ取得
st.size();

// lower_bound: 以上で最小の要素
auto lb = st.lower_bound(7);

// 最小・最大
int mn = *st.begin();
int mx = *st.rbegin();

multiset<int> mst;

mst.insert(5);
mst.insert(5);
mst.insert(2);

// 1個だけ消す（重要）
mst.erase(mst.find(5));

// 全削除はこれ
mst.erase(5);

注意: erase(value) は一致する全要素を消す。 1個だけ消したいなら find して iterator を渡す。また set はランダムアクセス不可（vectorみたいに st[i] はできない）。

map / multimap

用途: キーと値の対応をソート順で保持する

計算量: 基本操作は O(log N)。辞書、頻度表、座標圧縮後の管理に便利。

map<string, int> mp;
mp["apple"]++;
mp["banana"] = 3;

if (mp.count("apple")) {
    // 存在確認
}

for (auto &[key, value] : mp) {
    // 昇順に巡回
}

注意: operator[] は存在しないキーを作る。参照だけしたいなら at や find を使う。

unordered_map / unordered_set

用途: ハッシュベースの高速な辞書・集合

計算量: 平均 O(1)、最悪 O(N)。速いが、順序は保証されない。

unordered_map<long long, int> ump;
ump[123456789LL]++;

unordered_set<string> us;
us.insert("alpha");

注意: ハッシュ衝突が多いと遅くなることがある。必要なら reserve を使って再ハッシュを減らす。

count / find / contains

用途: 存在確認を素早く書く

計算量: set/map は O(log N)、unordered 系は平均 O(1)。 contains は C++20 で書き味がよい。

if (st.count(x)) { /* 存在 */ }

auto it = mp.find(key);
if (it != mp.end()) {
    // it->second を使う
}

if (us.contains("hello")) {
    // C++20
}

stack / queue / deque / heap

stack / queue / deque

用途: LIFO / FIFO / 両端キュー

計算量: 基本操作はすべて O(1)。 BFS、単調スタック、スライディングウィンドウで頻出。

// ===== stack =====
stack<int> st;

st.push(10);      // 要素を追加
st.push(20);

int x = st.top(); // 一番上を見る（20）
st.pop();         // 一番上を削除

bool empty = st.empty(); // 空か判定
size_t sz = st.size();   // 要素数

// ===== queue =====
queue<int> q;

q.push(10);        // 後ろに追加
q.push(20);

int front = q.front(); // 先頭を見る（10）
q.pop();               // 先頭を削除

bool empty2 = q.empty();
size_t sz2 = q.size();

// ===== deque =====
deque<int> dq;

dq.push_front(10); // 前に追加
dq.push_back(20);  // 後ろに追加

int first = dq.front(); // 先頭
int last  = dq.back();  // 末尾

dq.pop_front();    // 前を削除
dq.pop_back();     // 後ろを削除

注意: queue は前からしか取り出せない。両端を触りたいなら deque。

priority_queue

用途: 最大値・最小値を高速に取り出すヒープ

計算量: 追加・取り出しともに O(log N)、先頭参照は O(1)。ダイクストラ法の相棒。

priority_queue<int> pq; // 最大ヒープ
pq.push(3);
pq.push(10);
int mx = pq.top();
pq.pop();

priority_queue<int, vector<int>, greater<int>> minpq; // 最小ヒープ

注意: priority_queue は中身の直接更新が苦手。減少キーは「新しい値を push して古いものを無視する」実装が多い。

bit・bitset

ビット演算の基本

用途: 集合圧縮・状態管理・高速判定

計算量: すべて O(1)。「何桁まで扱うか」に注意したい。

int x = 1 << 3;     // 8
bool on = (mask & (1 << i)) != 0;
mask |= (1 << i);    // 立てる
mask ^= (1 << i);    // 反転
mask &= ~(1 << i);   // 落とす

注意: 1 << 31 のような式は型に注意。1LL を使う場面が多い。

popcount / ctz / bitset

用途: 立っているビット数・末尾の0の数・固定長ビット集合

計算量: popcount や ctz は定数時間に近い命令で動くことが多い。 bitset はサイズ固定のときに強い。

int cnt = __builtin_popcount((unsigned)x);
int tz = __builtin_ctz((unsigned)x); // x != 0 が必要

bitset<1000> bs;
bs.set(3);
bs.reset(3);
bool ok = bs.test(3);
bs.flip();

注意: ctz 系は 0 を渡すと未定義。bitset はコンパイル時サイズ固定である点が重要。

数学系

gcd / lcm

用途: 最大公約数・最小公倍数

計算量: gcd は O(log min(A,B))。 lcm はオーバーフローに注意。

long long g = gcd(a, b);
long long l = a / gcd(a, b) * b;

注意: a * b を先にやると溢れる可能性がある。必ず割ってから掛ける。

pow / modpow

用途: 累乗計算・mod累乗

計算量: 繰り返し二乗法で O(log N)。競プロでは mod つきが本命。

long long powll(long long a, long long e) {
    long long r = 1;
    while (e) {
        if (e & 1) r *= a;
        a *= a;
        e >>= 1;
    }
    return r;
}

long long modpow(long long a, long long e, long long mod) {
    long long r = 1;
    while (e) {
        if (e & 1) r = r * a % mod;
        a = a * a % mod;
        e >>= 1;
    }
    return r;
}

注意: 乗算前の型幅に注意。long long でも危険なら __int128 を使う。

mod の扱い

用途: 負数処理・剰余の正規化

計算量: O(1)。見た目以上にバグの出やすい箇所。

long long norm(long long x, long long mod) {
    x %= mod;
    if (x < 0) x += mod;
    return x;
}

注意: C++ の % は負数で負の剰余を返しうる。数学的な mod と同一視しない。

factorial / fact_inv / nCr / nPr / nHr (mod)

用途: 階乗・階乗逆元・逆元・二項係数（組合せ）の前計算と高速クエリ

計算量: 前計算に O(N)、各クエリ（階乗・階乗逆元・二項係数・順列・重複組合せの取得）は O(1)。

vector<long long> fact, fact_inv;

// mx: 必要な最大値（Nなど）, mod: 割る数（素数前提）
void init_nCr(int mx, long long mod) {
    fact.assign(mx + 1, 1);
    fact_inv.assign(mx + 1, 1);
    vector<long long> inv(mx + 1, 1);
    for (int i = 2; i <= mx; i++) {
        fact[i] = fact[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        fact_inv[i] = fact_inv[i - 1] * inv[i] % mod;
    }
}

// 階乗 n!
long long get_fact(int n) {
    if (n < 0) return 0;
    return fact[n];
}

// 階乗の逆元 (n!)^-1
long long get_fact_inv(int n) {
    if (n < 0) return 0;
    return fact_inv[n];
}

// 組合せ nCr
long long nCr(int n, int r, long long mod) {
    if (r < 0 || r > n) return 0;
    return fact[n] * fact_inv[r] % mod * fact_inv[n - r] % mod;
}

// 順列 nPr
long long nPr(int n, int r, long long mod) {
    if (r < 0 || r > n) return 0;
    return fact[n] * fact_inv[n - r] % mod;
}

// 重複組合せ nHr
long long nHr(int n, int r, long long mod) {
    if (n == 0 && r == 0) return 1;
    if (n <= 0 || r < 0) return 0;
    return nCr(n + r - 1, r, mod);
}


//使用例
int main() {
    long long mod = 1000000007;
    int max_n = 200000; // 問題内で登場する最大の N

    // 1. クエリを呼ぶ前に必ず一度だけ前計算を走らせる
    init_nCr(max_n, mod);

    // 2. 必要なタイミングで各種関数を呼び出す (各 O(1))
    long long f5 = get_fact(5);         // 5! = 120
    long long fi5 = get_fact_inv(5);    // (5!)^-1 mod 1000000007
    long long ans1 = nCr(10, 3, mod);   // 10C3 = 120

    cout << "5! = " << f5 << endl;
    cout << "(5!)^-1 mod 10^9+7 = " << fi5 << endl;
    cout << "10C3 = " << ans1 << endl;
}

注意: init_nCr に渡す mx は、求める可能性のある最大の n （重複組合せ nHr の場合は n + r - 1）をカバーできるよう余裕を持ったサイズで呼び出すこと。

注意: この逆元計算のアルゴリズムは mod が素数であることを前提としている。素数でない場合は拡張ユークリッドの互除法を個別に呼ぶか、パスカルの三角形による O(N²) の DP でテーブルを作る。

prime factorization

用途: 素因数分解

計算量: 試し割りで O(√N)。 N ≤ 10¹² 程度なら実用的。

vector<pair<long long, int>> prime_factorize(long long n) {
    vector<pair<long long, int>> res;

    for (long long p = 2; p * p <= n; p++) {
        if (n % p != 0) continue;

        int cnt = 0;
        while (n % p == 0) {
            n /= p;
            cnt++;
        }
        res.push_back({p, cnt});
    }

    if (n > 1) res.push_back({n, 1});

    return res;
}

注意: ループ条件は p * p <= n。割り進めることで探索範囲も縮むため、実際の計算量はかなり軽い。

enumerate divisors

用途: 約数列挙

計算量: O(√N)。 N ≤ 10¹² 程度なら実用的。

vector<long long> enumerate_divisors(long long n) {
    vector<long long> res;

    for (long long i = 1; i * i <= n; i++) {
        if (n % i != 0) continue;

        res.push_back(i);
        // 重複しない場合のみ、ペアとなる約数も追加
        if (i * i != n) {
            res.push_back(n / i);
        }
    }

    // 小さい順に並び替える
    sort(res.begin(), res.end());
    
    return res;
}

注意: ループ条件は i * i <= n。約数 i が見つかった際、同時にペアとなる n / i も追加することで、探索範囲を大幅に削減（$O(\sqrt{N})$）をカバーできるよう余裕を持ったサイズで呼び出すこと。

sieve of eratosthenes (spf)

用途: 高速素数列挙・高速素因数分解

計算量: 前処理: O(N log log N)、クエリ: O(log N)。 N ≤ 10⁷ 程度なら高速に動作。

struct Sieve {
    vector<int> min_factor;
    vector<int> primes;

    Sieve(int n) : min_factor(n + 1) {
        for (int i = 0; i <= n; i++) min_factor[i] = i;
        for (int i = 2; i * i <= n; i++) {
            if (min_factor[i] == i) {
                for (int j = i * i; j <= n; j += i) {
                    if (min_factor[j] == j) {
                        min_factor[j] = i;
                    }
                }
            }
        }
        for (int i = 2; i <= n; i++) {
            if (min_factor[i] == i) primes.push_back(i);
        }
    }

    bool is_prime(int x) const {
        if (x < 2) return false;
        return min_factor[x] == x;
    }

    vector<pair<int, int>> factor(int x) const {
        vector<pair<int, int>> res;
        while (x > 1) {
            int p = min_factor[x];
            int cnt = 0;
            while (x % p == 0) {
                x /= p;
                cnt++;
            }
            res.push_back({p, cnt});
        }
        return res;
    }
};

int main() {
    // 1. まず、探索したい最大値（N）を指定して、篩（構造体）を初期化する
    // ※この時点で、1から1000000までの「最小の素因数（SPF）」がすべて計算されます（前処理）
    Sieve sieve(1000000);

    // 2. 素数判定 (is_prime) の使い方
    cout << sieve.is_prime(53) << endl;   // 1 (true)
    cout << sieve.is_prime(100) << endl;  // 0 (false)

    // 3. 高速素因数分解 (factor) の使い方
    // 例として「24」を素因数分解する (24 = 2^3 * 3^1)
    auto res1 = sieve.factor(24);
    cout << "24の素因数分解: ";
    for (auto p : res1) {
        cout << p.first << "^" << p.second << " ";
    }
    cout << endl; // 出力: 2^3 3^1

    // 例として「9973（素数）」を素因数分解する
    auto res2 = sieve.factor(9973);
    cout << "9973の素因数分解: ";
    for (auto p : res2) {
        cout << p.first << "^" << p.second << " ";
    }
    cout << endl; // 出力: 9973^1

    // 4. 列挙された素数リスト (primes) の使い方
    // 1000000以下の素数の個数を出力してみる
    cout << "1000000以下の素数の数: " << sieve.primes.size() << endl;

    return 0;
}

注意: 単なる素数列挙だけでなく、各数の「最小の素因数（SPF）」を配列に記録しておくことで、前処理後は各クエリ O(log X) での高速素因数分解が可能になる。

sin / cos / tan / atan2

用途: 三角関数・角度計算・座標幾何

計算量: O(1)。幾何問題、回転、ベクトル、偏角計算。定数倍が重め。

const double PI = acos(-1.0);

// degree → radian
double rad = deg * PI / 180.0;

// radian → degree
double deg = rad * 180.0 / PI;

double x = cos(rad);
double y = sin(rad);

double t = tan(rad);

// 点 (x, y) の偏角
double angle = atan2(y, x);

ラジアンと度数法: C++ の sin・cos・tan・atan・atan2 はすべてラジアンを使う。 180° = π rad、90° = π/2 rad。

注意: atan(y / x) ではなく atan2(y, x) を使う。象限を正しく判定でき、x = 0 も扱える。

acos / asin / atan

用途: 逆三角関数

計算量: O(1)。角度復元や幾何計算で使用。

double theta1 = acos(x);
double theta2 = asin(x);
double theta3 = atan(x);

// degree 表示
double deg = acos(x) * 180.0 / PI;

戻り値: acos は [0, π]、 asin は [-π/2, π/2]、 atan は (-π/2, π/2) の範囲を返す。

注意: acos・asin の引数は [-1, 1] の範囲でなければならない。誤差対策として clamp することが多い。

distance / hypot

用途: ユークリッド距離計算

計算量: O(1)。幾何問題の基本。

double dx = x2 - x1;
double dy = y2 - y1;

double dist = hypot(dx, dy);
// sqrt(dx * dx + dy * dy) と同等

利点: hypot は内部でオーバーフロー・アンダーフローに強く実装されている。

注意: 距離比較だけなら dx * dx + dy * dy のまま扱い、平方根を取らない方が速い。

floating point comparison

用途: 浮動小数点誤差対策

計算量: O(1)。実数計算では必須。

const double EPS = 1e-9;

bool equal(double a, double b) {
    return fabs(a - b) < EPS;
}

注意: double 同士を a == b で比較しない。誤差により期待通りにならないことがある。

探索・二分探索・前計算

二分探索

用途: ソート済み配列から条件を満たす位置を探す

計算量: O(log N)

int l = 0;
int r = n;

while (l < r) {
    int mid = l + (r - l) / 2;

    if (a[mid] >= x)
        r = mid;
    else
        l = mid + 1;
}

用途例: lower_bound、upper_bound、特定値の探索

めぐる式二分探索

用途: 単調な判定関数の境界値を探す

計算量: 判定関数を O(F) とすると全体 O(F log R)

long long ng = -1;
long long ok = 1e18;

while (ok - ng > 1) {
    long long mid = ng + (ok - ng) / 2;

    if (check(mid))
        ok = mid;
    else
        ng = mid;
}

用途例: 最小値探索、最大値探索、答えを二分探索する問題

注意: 「ok は条件を満たす」「ng は条件を満たさない」を常に維持する。 okとngの大小関係は固定すること。

bit全探索

用途: 部分集合をすべて列挙して、条件を満たす組み合わせを探す

計算量: O(2^N × N)

for (int mask = 0; mask < (1 << N); mask++) {

    for (int i = 0; i < N; i++) {
        if (mask & (1 << i)) {
            // 判定・計算をする
        }
    }
}

用途例: 全列挙、部分集合和、組み合わせ探索、ナップサックの小規模版

注意: 1 << N は N >= 31 で危険なので、必要なら 1LL << N を使う。

累積和 / imos

用途: 区間加算・区間問い合わせを前処理で高速化

計算量: 前処理 O(N)、各問い合わせ O(1)。区間操作が多いときの大定番。

vector<long long> sum(n + 1, 0);
for (int i = 0; i < n; i++) sum[i + 1] = sum[i] + a[i];

// [l, r) の和
long long x = sum[r] - sum[l];

vector<long long> diff(n + 1, 0);
diff[l] += 1;
diff[r] -= 1;

注意: インデックスの半開区間 [l, r) を統一すると事故が減る。

座標圧縮

用途: 大きい値域を連番に潰して扱う

計算量: ソート O(N log N)、各値の変換 O(log N) または O(1)。区間や点を扱う問題で強い。

vector<long long> xs = {10, 100, 1000};
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());

auto get_id = [&](long long x) {
    return lower_bound(xs.begin(), xs.end(), x) - xs.begin();
};

注意: unique の前にソートが必要。

ランレングス圧縮 (RLE)

用途: 連続する同じ値をまとめて扱う

計算量: O(N)。文字列や配列の連続している区間を圧縮。

vector<pair<char, long long>> rle;

for (int i = 0; i < N; ) {
    int j = i;
    while (j < N && S[j] == S[i]) j++;

    rle.push_back({S[i], j - i});
    i = j;
}

例: aaabbcccc → {('a',3), ('b',2), ('c',4)}

HTML

尺取法 (Two Pointers)

用途: 条件を満たす区間（部分配列）の列挙や最長・最短の長さを求める

計算量: O(N)。右端と左端のポインタがそれぞれ単調増加（右にしか進まない）するため、配列を最大2周するだけで済む。

int right = 0;
long long sum = 0; // 区間の状態を管理する変数（例: 総和）

for (int left = 0; left < N; left++) {
    // right を進められるだけ進める
    while (right < N && /* rightを追加しても条件を満たすか */) {
        // sum に A[right] を加算するなど、状態を更新
        right++;
    }

    // ここで [left, right) は left を左端とする最大の条件を満たす区間
    // ans += (right - left); などの処理を行う

    // left を次へ進めるための準備
    if (right == left) {
        right++; // right が left に追い抜かれないようにする
    } else {
        // sum から A[left] を減算するなど、状態を戻す
    }
}

例: 合計がK以下となる連続部分配列の数を数え上げる場合などに威力を発揮。

データ構造

Union-Find / DSU

用途: 連結成分の管理・同値類の統合

計算量: ほぼ O(α(N))。実用上はほぼ定数だが、最悪ケースを避けるには経路圧縮と union by size/rank が重要。

// Union-Find の構造体
struct UnionFind {
    vector<int> parent; // parent[i] は i の親要素。i が根（リーダー）の場合は -1
    vector<int> siz;    // siz[i] は i を根とするグループの要素数

    // 構造体の初期化（要素数 N で作成）
    UnionFind(int n) {
        parent.assign(n, -1); // 最初はみんな自分が根（-1）
        siz.assign(n, 1);     // 最初はみんなサイズ 1
    }

    // 1. Find: 要素 x の根（リーダー）を返す
    int find(int x) {
        if (parent[x] == -1) return x; // 自分が根なら自分を返す
        // 経路圧縮：親を「根」に直接繋ぎ変えながら再帰的に探す
        return parent[x] = find(parent[x]); 
    }

    // 2. Union: 要素 x と要素 y のグループを合体させる
    bool unite(int x, int y) {
        // それぞれのリーダーを探す
        int root_x = find(x);
        int root_y = find(y);

        // すでに同じグループなら何もしない
        if (root_x == root_y) return false;

        // Union by Size: 小さい方を大きい方の下に合体させる
        if (siz[root_x] < siz[root_y]) {
            swap(root_x, root_y); // 常に root_x の方がサイズが大きくなるようにする
        }

        // root_y の親を root_x にする（root_x が新しいボス）
        parent[root_y] = root_x;
        siz[root_x] += siz[root_y]; // サイズを合算する
        return true;
    }

    // 3. Same: 要素 x と要素 y が同じグループに属するか判定
    bool same(int x, int y) {
        return find(x) == find(y);
    }

    // 4. Size: 要素 x が属するグループのサイズ（要素数）を返す
    int size(int x) {
        return siz[find(x)];
    }
};

int main() {
    // 5つの要素 (0, 1, 2, 3, 4) で Union-Find を作成
    UnionFind uf(5);

    // グループを繋げてみる
    uf.unite(0, 1); // 0 と 1 を同じグループに
    uf.unite(2, 3); // 2 と 3 を同じグループに

    // 同じグループか判定
    cout << "0 と 1 は同じ？: " << (uf.same(0, 1) ? "Yes" : "No") << endl; // Yes
    cout << "0 と 2 は同じ？: " << (uf.same(0, 2) ? "Yes" : "No") << endl; // No

    // さらに繋げる
    uf.unite(1, 3); // 0-1 グループ と 2-3 グループが合体！

    cout << "合体後、0 と 2 は同じ？: " << (uf.same(0, 2) ? "Yes" : "No") << endl; // Yes
    cout << "0 がいるグループのサイズ: " << uf.size(0) << endl; // 4 (0, 1, 2, 3 がいるので)

    return 0;
}

Fenwick Tree / BIT

用途: 点更新・区間和を高速に扱う

計算量: 更新 O(log N)、prefix sum O(log N)。「配列の和を頻繁に取りたい」ならまず候補になる。

struct BIT {
    int n;
    vector<long long> bit;
    BIT(int n): n(n), bit(n + 1, 0) {}

    void add(int idx, long long val) {
        for (++idx; idx <= n; idx += idx & -idx) bit[idx] += val;
    }

    long long sum(int idx) { // [0, idx)
        long long s = 0;
        for (; idx > 0; idx -= idx & -idx) s += bit[idx];
        return s;
    }
};

int main() {
    // 1. 初期化：要素数 5 の BIT を作る
    int N = 5;
    BIT b(N);

    // 2. 初期値をセット（加算）する
    // 元の配列イメージ: [10, 20, 30, 40, 50]
    b.add(0, 10);
    b.add(1, 20);
    b.add(2, 30);
    b.add(3, 40);
    b.add(4, 50);

    // 3. 先頭からの区間和を求めてみる
    // 例：インデックス 0 から 2 までの合計（10 + 20 + 30 = 60）
    // ※ sum(3) なので、[0, 3) となり、インデックス 0, 1, 2 が対象になります
    cout << "区間 [0, 3) の合計: " << b.sum(3) << endl; // 出力: 60

    // 例：配列全体の合計（10 + 20 + 30 + 40 + 50 = 150）
    cout << "全体の合計: " << b.sum(5) << endl; // 出力: 150

    // 4. 途中の任意の区間 [l, r) の和を求める方法
    // 例：インデックス 1 から 3 までの合計（20 + 30 + 40 = 90）を求めたい場合
    // [0, 4) の総和から、余分な [0, 1) の総和を引き算します
    int l = 1, r = 4;
    long long section_sum = b.sum(r) - b.sum(l);
    cout << "区間 [1, 4) の合計: " << section_sum << endl; // 出力: 90

    // 5. 値を途中で更新（加算）する
    // インデックス 2 に「+70」する（もともと 30 なので、30 + 70 = 100 になる）
    // 元の配列イメージ: [10, 20, 100, 40, 50] になる
    b.add(2, 70);

    // 6. 更新後に、もう一度同じ区間の合計を求めてみる
    // インデックス 1 から 3 までの合計（20 + 100 + 40 = 160）
    cout << "更新後の区間 [1, 4) の合計: " << b.sum(4) - b.sum(1) << endl; // 出力: 160

    return 0;
}

注意: BIT は区間更新より点更新向き。区間更新は差分や別テクニックを考える。

SegmentTree

用途: 点更新・区間クエリの汎用データ構造（ラムダ式で演算を注入）

計算量: 更新・クエリともに O(log N)。内部は 1-indexed の配列。

template <class T, class F>
struct SegmentTree {
    int n;
    vector<T> data;
    T e;
    F op;

    // コンストラクタ
    SegmentTree(int sz, T e, F op) : e(e), op(op) {
        n = 1;
        while (n < sz) n <<= 1;
        data.assign(2 * n, e);
    }

    // 配列から初期構築 O(N)
    void build(const vector<T>& v) {
        for (int i = 0; i < (int)v.size(); i++) data[i + n] = v[i];
        for (int i = n - 1; i > 0; i--) data[i] = op(data[2 * i], data[2 * i + 1]);
    }

    // 点更新: p番目の要素を x に更新
    void update(int p, T x) {
        p += n;
        data[p] = x;
        while (p > 1) {
            p >>= 1;
            data[p] = op(data[2 * p], data[2 * p + 1]);
        }
    }

    // 区間クエリ: [l, r) の演算結果を取得
    T query(int l, int r) {
        T sml = e, smr = e;
        l += n; r += n;
        while (l < r) {
            if (l & 1) sml = op(sml, data[l++]);
            if (r & 1) smr = op(data[--r], smr);
            l >>= 1; r >>= 1;
        }
        return op(sml, smr);
    }
};

int main() {
    int N = 5;
    long long INF = 1e18;
    vector<long long> A = {10, 20, 30, 40, 50};

    // 1. 演算をラムダ式で定義（例: 区間最小値 RMQ）
    auto op = [](long long a, long long b) { return min(a, b); };

    // 2. セグメント木の初期化 (C++17なら型の明記不要でスッキリ！)
    // SegmentTree(要素数, 単位元, 演算関数)
    SegmentTree seg(N, INF, op);
    seg.build(A);

    cout << "区間 [1, 4) の最小値: " << seg.query(1, 4) << endl; // 20
    
    seg.update(2, 5); // インデックス2を 5 に更新
    
    cout << "更新後の区間 [1, 4) の最小値: " << seg.query(1, 4) << endl; // 5
}

LazySegmentTree

用途: 区間更新・区間加算などに対応した汎用遅延セグメント木

計算量: 更新・クエリともに O(log N)。再帰方式による実装。ラムダ式で op, mapping, composition を注入して動作を決定する。

template <class T, class E, class F, class G, class H>
struct LazySegmentTree {
    int n;
    vector<T> data;
    vector<E> lazy;
    T T_e;      // データの単位元
    E E_e;      // 遅延メモの単位元（空であることを示す値）
    F op;          // データ同士の合成
    G mapping;     // データへの遅延メモの適用
    H composition; // 遅延メモ同士の合成

    LazySegmentTree(int sz, T T_e, E E_e, F op, G mapping, H composition) 
        : T_e(T_e), E_e(E_e), op(op), mapping(mapping), composition(composition) {
        n = 1;
        while (n < sz) n <<= 1;
        data.assign(2 * n, T_e);
        lazy.assign(2 * n, E_e);
    }

    // 遅延評価（伝播）
    void eval(int k, int l, int r) {
        if (lazy[k] == E_e) return;
        data[k] = mapping(lazy[k], data[k]);
        if (r - l > 1) { // 子ノードがあればメモを下へ伝播
            lazy[2 * k] = composition(lazy[k], lazy[2 * k]);
            lazy[2 * k + 1] = composition(lazy[k], lazy[2 * k + 1]);
        }
        lazy[k] = E_e; // 自身のメモを空にする
    }

    // 区間更新 [a, b) を x で作用
    void update(int a, int b, E x, int k = 1, int l = 0, int r = -1) {
        if (r < 0) r = n;
        eval(k, l, r);
        if (b <= l || r <= a) return; // 完全に範囲外
        if (a <= l && r <= b) {       // 完全にすっぽり含まれる
            lazy[k] = composition(x, lazy[k]);
            eval(k, l, r);
            return;
        }
        // 一部だけ被る場合
        int mid = (l + r) / 2;
        update(a, b, x, 2 * k, l, mid);
        update(a, b, x, 2 * k + 1, mid, r);
        data[k] = op(data[2 * k], data[2 * k + 1]);
    }

    // 区間取得 [a, b)
    T query(int a, int b, int k = 1, int l = 0, int r = -1) {
        if (r < 0) r = n;
        eval(k, l, r);
        if (b <= l || r <= a) return T_e;
        if (a <= l && r <= b) return data[k];
        int mid = (l + r) / 2;
        T vl = query(a, b, 2 * k, l, mid);
        T vr = query(a, b, 2 * k + 1, mid, r);
        return op(vl, vr);
    }
};

int main() {
    int N = 5;
    long long LINF = 1e18;

    // パターン例: 区間更新 (Range Update) & 区間最大値 (Range Max) の設定
    auto op = [](long long a, long long b) { return max(a, b); };
    
    // mapping(メモf, 現在のデータx): メモが空(-LINF)じゃなければ上書き
    auto mapping = [LINF](long long f, long long x) { return (f == -LINF ? x : f); };
    
    // composition(新しいメモf_new, 古いメモf_old): 新しいメモで完全に上書き
    auto composition = [LINF](long long f_new, long long f_old) { return (f_new == -LINF ? f_old : f_new); };

    // 初期化 (CTADによる自動型推論)
    // LazySegmentTree(要素数, データ単位元, メモ単位元, op, mapping, composition)
    LazySegmentTree lazy_seg(N, -LINF, -LINF, op, mapping, composition);

    // 区間 [1, 4) をすべて 25 に更新
    lazy_seg.update(1, 4, 25);

    // 区間 [0, 3) の最大値を取得
    cout << "区間 [0, 3) の最大値: " << lazy_seg.query(0, 3) << endl; // 25
}

グラフ

BFS / DFS

用途: 到達可能性・距離・木探索

計算量: 隣接リストなら O(V + E)。 BFS は最短路の「辺数」、DFS は構造把握に向く。

// ===== BFS =====
// start から各頂点への最短距離(辺数)を求める
vector<int> bfs(const vector<vector<int>>& graph, int start) {
    int n = graph.size();

    vector<int> dist(n, -1);
    queue<int> q;

    dist[start] = 0;
    q.push(start);

    while (!q.empty()) {
        int v = q.front();
        q.pop();

        for (int next : graph[v]) {
            if (dist[next] != -1) continue;

            dist[next] = dist[v] + 1;
            q.push(next);
        }
    }

    return dist;
}

// ===== DFS (再帰) =====
void dfs(const vector<vector<int>>& graph,
         vector<bool>& seen,
         int v) {

    seen[v] = true;

    for (int next : graph[v]) {
        if (seen[next]) continue;
        dfs(graph, seen, next);
    }
}

// 呼び出し例
int main() {
    vector<vector<int>> graph = {
        {1, 2},     // 0
        {0, 3},     // 1
        {0, 3},     // 2
        {1, 2, 4},  // 3
        {3}         // 4
    };

    // BFS
    vector<int> dist = bfs(graph, 0);

    // DFS
    vector<bool> seen(graph.size(), false);
    dfs(graph, seen, 0);
}

注意: 再帰DFSは深い木でスタックオーバーフローの危険がある。必要なら iterative DFS を使う。

Dijkstra

用途: 非負辺の単一始点最短路

計算量: 優先度付きキューで O((V + E) log V) が典型。負辺があると使えない。

vector<ll> Dijkstra(ll N, ll start, vector<vector<pair<ll, ll>>> G) {
  // 隣接リストGは{頂点番号,重み}で与えている
  vector<ll> dist(N, INF);
  priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>>
      todo;
  todo.push({0, start});
  dist[start] = 0;

  while (todo.empty() == false) {
    ll d = todo.top().first;
    ll m = todo.top().second;
    todo.pop();

    if (d > dist[m]) {
      continue;
    }

    rep(i, G[m].size()) {
      if (d + G[m][i].second < dist[G[m][i].first]) {
        dist[G[m][i].first] = d + G[m][i].second;
        todo.push({d + G[m][i].second, G[m][i].first});
      }
    }
  }
  return dist;
}

注意: 典型的に「古い状態を無視」する実装になる。if (d != dist[v]) continue; はほぼ必須。

Warshall-Floyd

用途: 全点対間最短経路（全頂点間の最短距離）

計算量: O(V^3) が典型。負の辺が含まれていても動作するが、負の閉路があると正しく計算できない。

void WarshallFloyd(ll N, vector<vector<ll>> &dist) {
  // dist[i][j] は頂点iからjへの辺の重み。初期値は dist[i][i] = 0、経路がない場合は INF
  rep(k, N) {
    rep(i, N) {
      rep(j, N) {
        if (dist[i][k] != INF && dist[k][j] != INF) {
          dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        }
      }
    }
  }
}

注意: 入力するのは、重みのグラフ。そのため、隣接行列を取る必要がある。グラフの辺数が多いときは全頂点でDijkstraをするより高速。

Topological Sort

用途: DAG の順序付け

計算量: O(V + E)。依存関係のある処理順を作るときに使う。

queue<int> q;
vector<int> indeg(n);
for (int i = 0; i < n; i++) if (indeg[i] == 0) q.push(i);

vector<int> ord;
while (!q.empty()) {
    int v = q.front(); q.pop();
    ord.push_back(v);
    for (int to : g[v]) {
        if (--indeg[to] == 0) q.push(to);
    }
}

注意: ord の長さが n 未満なら閉路あり。

Strongly Connected Components (SCC)

用途: 有向グラフの強連結成分分解・閉路検出・DAG化

計算量: O(V + E)。 2回のDFS（コサラジュのアルゴリズム）を用いて有向グラフを強連結成分に分解する。

// 1回目のDFS: 帰りがけ順（バックトラック時）に頂点を記録
void SCC1(const vvl &graph, vb &seen, vl &V, ll v) {
    seen[v] = true;
    for (ll next : graph[v]) {
        if (seen[next] == true) {
            continue;
        }
        SCC1(graph, seen, V, next);
    }
    V.push_back(v);
}

// 2回目のDFS: 逆方向グラフを用いて成分ごとに頂点を回収
void SCC2(const vvl &graph, vb &seen, ll v, vl &SCC_part) {
    seen[v] = true;
    for (ll next : graph[v]) {
        if (seen[next] == true) {
            continue;
        }
        SCC2(graph, seen, next, SCC_part);
    }
    SCC_part.push_back(v);
}

// =====ここから使い方=====
vvl G1(N), G2(N); // G1は順方向、G2は逆方向の隣接リスト
vb seen1(N, false);
vl V;
rep(i, N) {
    if (seen1[i] == false) {
        SCC1(G1, seen1, V, i);
    }
}

reverse(V.begin(), V.end());

vvl SCC;
vb seen2(N, false);
rep(i, N) {
    if (seen2[V[i]] == false) {
        vl SCC_part;
        SCC2(G2, seen2, V[i], SCC_part);
        SCC.push_back(SCC_part);
    }
}

// SCCのi行目がi番目の強連結成分の要素

注意: 二次元配列 SCC に格納されるグループの順序は、自動的に「トポロジカルソート順（上流から下流）」になる。成分を潰してDAGとしてDPを回す際は、そのまま 0 から順に遷移すればよい。

DP

1次元DP / 2次元DP

用途: 状態遷移を表にして解く

計算量: 状態数 × 遷移数。まず状態設計、その次に遷移設計。

vector<long long> dp(n + 1, INF);
dp[0] = 0;
for (int i = 0; i < n; i++) {
    dp[i + 1] = min(dp[i + 1], dp[i] + cost[i]);
}

注意: 配列の初期値と遷移順序を混同しない。INF を使うなら十分大きい値にする。

Knapsack の典型

用途: 重さ・価値の最適化

計算量: 0/1 ナップサックは O(NW)、価値DPは条件次第で O(NV)。重いので制約確認が重要。

vector<long long> dp(W + 1, -INF);
dp[0] = 0;
for (auto [w, val] : items) {
    for (int j = W; j >= w; j--) {
        dp[j] = max(dp[j], dp[j - w] + val);
    }
}

注意: 更新ループの向きが重要。0/1 は逆順、無制限は順方向が基本。

形式的冪級数 (FPS: Formal Power Series)

AtCoder Library (ACL) の convolution を内部で利用した FPS 演算ライブラリ。多項式の加減乗除をはじめ、微積分、逆元 (inv)、対数 (log)、指数 (exp)、累乗 (pow) の基本操作を含む。

FPS クラス実装

用途: O(N log N) での高度な多項式演算を一通り完結させる

計算量: 加減算や微積分は O(N)。乗算、inv、exp、log、pow はいずれも O(N log N) です。
前提: #include <atcoder/all> が必要です。ダブリングによるニュートン法で実装しています。

template <typename mint>
struct FPS : std::vector<mint> {
    using std::vector<mint>::vector;
    FPS(const std::vector<mint>& v) { this->assign(v.begin(), v.end()); }

    // 指定した次数までで切り打ち（リサイズ）
    FPS pre(int deg) const {
        FPS res(*this);
        res.resize(deg);
        return res;
    }

    FPS& operator+=(const FPS& r) {
        if (r.size() > this->size()) this->resize(r.size());
        for (int i = 0; i < (int)r.size(); i++) (*this)[i] += r[i];
        return *this;
    }

    FPS& operator-=(const FPS& r) {
        if (r.size() > this->size()) this->resize(r.size());
        for (int i = 0; i < (int)r.size(); i++) (*this)[i] -= r[i];
        return *this;
    }

    // ACL の convolution を使った乗算
    FPS& operator*=(const FPS& r) {
        if (this->empty() || r.empty()) {
            this->clear();
            return *this;
        }
        auto res = atcoder::convolution(*this, r);
        this->assign(res.begin(), res.end());
        return *this;
    }

    FPS operator+(const FPS& r) const { return FPS(*this) += r; }
    FPS operator-(const FPS& r) const { return FPS(*this) -= r; }
    FPS operator*(const FPS& r) const { return FPS(*this) *= r; }

    FPS operator*(mint v) const {
        FPS res(*this);
        for (int i = 0; i < (int)res.size(); i++) res[i] *= v;
        return res;
    }
    FPS& operator*=(mint v) {
        for (int i = 0; i < (int)this->size(); i++) (*this)[i] *= v;
        return *this;
    }

    // 微分
    FPS deriv() const {
        if (this->empty()) return FPS();
        FPS res(this->size() - 1);
        for (int i = 1; i < (int)this->size(); i++) res[i - 1] = (*this)[i] * i;
        return res;
    }

    // 積分
    FPS integral() const {
        if (this->empty()) return FPS();
        FPS res(this->size() + 1);
        res[0] = 0;
        for (int i = 0; i < (int)this->size(); i++) res[i + 1] = (*this)[i] / (i + 1);
        return res;
    }

    // 逆元 (Inverse)
    FPS inv(int deg = -1) const {
        if (deg == -1) deg = this->size();
        FPS res{(*this)[0].inv()};
        for (int d = 1; d < deg; d *= 2) {
            FPS f = pre(2 * d);
            FPS g = res;
            f *= g;
            f.resize(2 * d);
            for (int i = 0; i < 2 * d; i++) f[i] = -f[i];
            f[0] += 2;
            f *= g;
            f.resize(2 * d);
            res = f;
        }
        return res.pre(deg);
    }

    // 対数 (Log) : F[0] == 1 が必須
    FPS log(int deg = -1) const {
        if (deg == -1) deg = this->size();
        FPS f = deriv();
        FPS g = inv(deg);
        f *= g;
        return f.integral().pre(deg);
    }

    // 指数 (Exp) : F[0] == 0 が必須
    FPS exp(int deg = -1) const {
        if (deg == -1) deg = this->size();
        FPS res{1};
        for (int d = 1; d < deg; d *= 2) {
            FPS f = res.log(2 * d);
            f[0] -= 1;
            for (int i = 0; i < 2 * d; i++) f[i] = -f[i];
            FPS g = pre(2 * d);
            f += g;
            res *= f;
            res.resize(2 * d);
        }
        return res.pre(deg);
    }

    // 累乗 (Pow) : 定数項が0の場合（先行ゼロ）にも対応
    FPS pow(long long k, int deg = -1) const {
        if (deg == -1) deg = this->size();
        if (k == 0) {
            FPS res(deg, 0);
            if (deg > 0) res[0] = 1;
            return res;
        }
        for (int i = 0; i < (int)this->size(); i++) {
            if ((*this)[i] != 0) {
                mint rev = (*this)[i].inv();
                FPS f(*this);
                for (int j = 0; j < (int)f.size(); j++) f[j] *= rev;
                f = f.pre(deg);
                f.erase(f.begin(), f.begin() + i);
                f = f.log(deg);
                for (int j = 0; j < (int)f.size(); j++) f[j] *= k;
                f = f.exp(deg);
                for (int j = 0; j < (int)f.size(); j++) f[j] *= (*this)[i].pow(k);
                
                FPS res(deg, 0);
                long long shift = i * k;
                if (shift >= deg) return res;
                for (int j = 0; j < (int)f.size() && j + shift < deg; j++) {
                    res[j + shift] = f[j];
                }
                return res;
            }
        }
        return FPS(deg, 0);
    }
};

using mint = modint998244353;
using fps = FPS<mint>;

使い方

用途: 実戦での基本的な呼び出し方・初期化方法

std::vector を継承しているため、size() や resize() などのメソッドがそのまま使える。特定の次数（mod x^d）まで計算したい場合は、引数に deg を指定する。

// 初期化 (1 + 2x + 3x^2 と 4 + 5x)
fps F = {1, 2, 3};
fps G = {4, 5};

// 四則演算 (乗算は自動でサイズが伸びます)
fps add = F + G;
fps sub = F - G;
fps mul = F * G; 

// N 次未満 (mod x^N) に切り詰める場合は pre() を使う
int N = 10;
fps pre_mul = (F * G).pre(N);

// 逆元: F(x) * I(x) = 1 (mod x^N) となる I(x)
// F[0] != 0 である必要があります
fps inv = F.inv(N);

// 微分と積分
fps deriv = F.deriv();
fps integral = F.integral();

// 対数・指数・累乗
// log は F[0] == 1 が必須条件
fps log_F = F.log(N); 
// exp は F[0] == 0 が必須条件
fps exp_F = F.exp(N); 

// F(x) の K 乗を mod x^N で求める
// 定数項が0 (例: x^2 + x^3) でも内部で適切にシフト処理されます
long long K = 1000000007;
fps pow_F = F.pow(K, N);

// 要素へのアクセス (vector と同じ)
cout << F[0].val() << "\n";

雑多に便利なもの

pair / tuple / structured binding

用途: 複数値をまとめて持つ

計算量: O(1)。グラフの辺や座標、複数返り値の受け取りで多用する。

// pair の定義
pair<int, int> p = {1, 2};
auto q = make_pair(3, 4);

// 要素の読み出し
cout << p.first << " " << p.second << "\n";

// structured binding (C++17)
auto [x, y] = p;
cout << x << " " << y << "\n";

// tuple の定義
tuple<int, int, int> t = {1, 2, 3};

// tuple の分解
auto [a, b, c] = t;

// tuple の要素取得
cout << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << "\n";

注意: 比較可能な型なら pair/tuple は辞書順で比較される。

accumulate / iota / unique

用途: 合計・連番生成・重複除去の基本

計算量: いずれも O(N)。「書けるのに手で書くのが面倒」な場面で強い。

long long s = accumulate(v.begin(), v.end(), 0LL);

vector<int> id(n);
iota(id.begin(), id.end(), 0);

sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());

min_element / max_element / clamp

用途: 最小値・最大値・範囲制限

計算量: O(N)。「要素全体を見る」基本操作を安全に書ける。

auto it = min_element(v.begin(), v.end());
auto jt = max_element(v.begin(), v.end());

int y = clamp(x, 0, 100);

注意: 空配列に対して min_element や max_element を呼ばない。

lambda

用途: その場で関数を定義する

計算量: 関数そのものは O(1)、中身に依存。再帰・比較関数・探索の局所補助でよく使う。

auto f = [&](int x) {
    return x * x;
};

alphabet index (a-z)

用途: 小文字アルファベットの何番目かを取得

計算量: O(1)。文字をASCII値から直接計算する。

// a=1, b=2, ..., z=26
int alphabetIndexLower(char c) {
    if ('a' <= c && c <= 'z') {
        return c - 'a' + 1;
    }
    return -1; // 範囲外
}

// 使用例
char c = 'c';
cout << alphabetIndexLower(c) << "\n"; // 3

注意: 小文字専用のため、大文字は無効扱い。

alphabet index (A-Z)

用途: 大文字アルファベットの何番目かを取得

計算量: O(1)。文字をASCII値から直接計算する。

// A=1, B=2, ..., Z=26
int alphabetIndexUpper(char c) {
    if ('A' <= c && c <= 'Z') {
        return c - 'A' + 1;
    }
    return -1; // 範囲外
}

// 使用例
char c = 'C';
cout << alphabetIndexUpper(c) << "\n"; // 3

注意: 大文字専用のため、小文字は無効扱い。