高速入出力と座標圧縮

大量のデータ処理を行う際、標準的な入出力関数はボトルネックになることがあります。以下では、カスタム関数による高速化と、std ライブラリを使用した最適化の両方を示します。

#include <bits/stdc++.h>
using namespace std;

// カスタム関数による高速入力
inline int fastRead() {
    int val = 0;
    char ch = getchar();
    bool neg = false;
    while (!isdigit(ch)) {
        if (ch == '-') neg = true;
        ch = getchar();
    }
    while (isdigit(ch)) {
        val = val * 10 + (ch - '0');
        ch = getchar();
    }
    return neg ? -val : val;
}

// cin/cout の高速化設定を使用するケース
void optimizeIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    int n = fastRead();
    int result = 0;
    for (int i = 0; i < n; ++i) {
        int inputVal = fastRead();
        result ^= inputVal;
    }
    // 結果出力は printf または cout を使用可能
    printf("%d\n", result);
    return 0;
}

値の範囲が大きい場合や疎な状態を扱う際は、座標圧縮（離散化）によりデータサイズを削減できます。

void coordinateCompression(vector<int>& arr) {
    vector<int> sortedVals = arr;
    sort(sortedVals.begin(), sortedVals.end());
    sortedVals.erase(unique(sortedVals.begin(), sortedVals.end()), sortedVals.end());
    
    for (int &val : arr) {
        val = lower_bound(sortedVals.begin(), sortedVals.end(), val) - sortedVals.begin();
    }
}

数学的演算

素数判定と篩法

エラトステネスの篩はシンプルですが、線形篩法はより効率的に素数を列挙できます。

// 線形篩法の実装例
const int MAX_N = 100000001;
bool isComposite[MAX_N];
vector<int> primes;

void linearSieve(int limit) {
    fill(isComposite, isComposite + limit + 1, false);
    for (int i = 2; i <= limit; ++i) {
        if (!isComposite[i]) {
            primes.push_back(i);
        }
        for (int p : primes) {
            if (i * p > limit) break;
            isComposite[i * p] = true;
            if (i % p == 0) break; 
        }
    }
}

Modular Exponentiation

巨大な冪乗を計算する際の標準的な手法です。

long long modPow(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = (result * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return result;
}

グラフ理論

グラフの表現方法

• 隣接行列: dense なグラフ向け
• 隣接リスト: sparse なグラフ向け（一般的）
• 辺集合: Kruskal 法等の特定用途向け

struct Edge {
    int to, cost;
};
vector<vector<Edge>> adjList;

void addEdge(int u, int v, int w) {
    adjList[u].push_back({v, w});
    // 無向図の場合：adjList[v].push_back({u, w});
}

最短経路問題

ダイクストラ法（優先度付きキュー最適化）

const long long INF = 1e18;
vector<long long> dist;
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;

void dijkstra(int startNode, int numNodes) {
    dist.assign(numNodes, INF);
    dist[startNode] = 0;
    pq.push({0, startNode});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dist[u]) continue;

        for (auto& edge : adjList[u]) {
            if (dist[edge.to] > dist[u] + edge.cost) {
                dist[edge.to] = dist[u] + edge.cost;
                pq.push({dist[edge.to], edge.to});
            }
        }
    }
}

Bellman-Ford と SPFA

負の重みを持つ辺がある場合に適しています。SPFA は平均的に高速ですが、最悪ケースは O(V・E) です。

Floyd-Warshall アルゴリズム

全点対間最短距離を求めるための DP 手法です。

void floydWarshall(int N, vector<vector<int>>& d) {
    for (int k = 0; k < N; ++k) {
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}

最小全域木 (MST)

Kruskal 法

struct DSU {
    vector<int> parent;
    DSU(int n) : parent(n) { iota(parent.begin(), parent.end(), 0); }
    int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
    bool unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return false;
        parent[y] = x;
        return true;
    }
};

long long kruskal(int V, const vector<tuple<int, int, int>>& edges) {
    sort(edges.begin(), edges.end());
    DSU dsu(V);
    long long mstWeight = 0;
    for (auto& [cost, u, v] : edges) {
        if (dsu.unite(u, v)) {
            mstWeight += cost;
        }
    }
    return mstWeight;
}

Prim 法（ヒープ利用）

dense なグラフでは有効ですが、通常は隣接リストと PriorityQueue を組み合わせた実装が使われます。

Tarjan アルゴリズム

橋（割点と連結性）や双連結成分の発見に用いられます。dfn (Discovery Time) と low (Low Link Value) を管理します。

int timer;
vector<int> dfn, low;
void tarjanDFS(int u, int parentEdgeIdx) {
    dfn[u] = low[u] = ++timer;
    for (int idx = head[u]; idx; idx = nxt[idx]) {
        if (idx == (parentEdgeIdx ^ 1)) continue; // 戻る辺を除外
        int v = to[idx];
        if (!dfn[v]) {
            tarjanDFS(v, idx);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u]) {
                // idx は橋である
            }
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

木構造のアルゴリズム

最近共通祖先 (LCA)

倍増法（Binary Lifting）を用いたオンラインアルゴリズムです。

const int LOGN = 20;
int up[LOGN][MAX_N];
int depth[MAX_N];

void dfsLCA(int u, int p, int d) {
    depth[u] = d;
    up[0][u] = p;
    for (int v : children[u]) {
        if (v != p) dfsLCA(v, u, d + 1);
    }
}

void precomputeLCA(int root, int n) {
    dfsLCA(root, root, 0);
    for (int k = 1; k < LOGN; ++k) {
        for (int i = 1; i <= n; ++i) {
            up[k][i] = up[k-1][up[k-1][i]];
        }
    }
}

int getLCA(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    for (int k = LOGN-1; k >= 0; --k) {
        if (depth[u] - (1 << k) >= depth[v]) {
            u = up[k][u];
        }
    }
    if (u == v) return u;
    for (int k = LOGN-1; k >= 0; --k) {
        if (up[k][u] != up[k][v]) {
            u = up[k][u];
            v = up[k][v];
        }
    }
    return up[0][u];
}

高度なデータ構造

二分ヒープ (Binary Heap)

手動実装が必要な場面もありますが、STL の priority_queue が一般的な代替手段です。

struct MinHeap {
    vector<int> heap;
    void push(int x) {
        heap.push_back(x);
        int i = heap.size() - 1;
        while (i > 0 && heap[(i - 1) / 2] > heap[i]) {
            swap(heap[(i - 1) / 2], heap[i]);
            i = (i - 1) / 2;
        }
    }
    int top() { return heap.empty() ? -1 : heap.front(); }
    void pop() {
        if (heap.empty()) return;
        heap[0] = heap.back();
        heap.pop_back();
        int i = 0;
        while (true) {
            int l = 2 * i + 1, r = 2 * i + 2, smallest = i;
            if (l < heap.size() && heap[l] < heap[smallest]) smallest = l;
            if (r < heap.size() && heap[r] < heap[smallest]) smallest = r;
            if (smallest == i) break;
            swap(heap[i], heap[smallest]);
            i = smallest;
        }
    }
};

セグメント木 (Segment Tree)

区間操作を高速に行うためのツリー構造です。遅延伝播（Lazy Propagation）を使用することで、区間更新も可能です。

template<typename T>
class SegmentTree {
    int size;
    vector<T> data;
    vector<T> lazy;
    T identity;

public:
    SegmentTree(int n, T id) : size(1), identity(id) {
        while (size < n) size *= 2;
        data.assign(2 * size, identity);
        lazy.assign(size, 0);
    }

    void apply(int node, T val) {
        data[node] += val; // 操作に応じたロジック
        lazy[node] += val;
    }

    void push(int node) {
        if (lazy[node] != 0) {
            apply(2 * node, lazy[node]);
            apply(2 * node + 1, lazy[node]);
            lazy[node] = 0;
        }
    }

    void update(int l, int r, T val) { update(l, r, val, 1, 0, size); }

    void update(int l, int r, T val, int node, int nl, int nr) {
        if (r < nl || nr < l) return;
        if (l <= nl && nr <= r) {
            apply(node, val);
            return;
        }
        push(node);
        int mid = (nl + nr) / 2;
        update(l, r, val, 2 * node, nl, mid);
        update(l, r, val, 2 * node + 1, mid + 1, nr);
        data[node] = merge(data[2 * node], data[2 * node + 1]);
    }

    T query(int l, int r) { return query(l, r, 1, 0, size); }

    T query(int l, int r, int node, int nl, int nr) {
        if (r < nl || nr < l) return identity;
        if (l <= nl && nr <= r) return data[node];
        push(node);
        int mid = (nl + nr) / 2;
        return merge(query(l, r, 2 * node, nl, mid),
                     query(l, r, 2 * node + 1, mid + 1, nr));
    }
};

Binary Indexed Tree (Fenwick Tree)

単点更新と累積和（またはその逆）に対して非常に効率的です。差分配列と組み合わせることで区間更新・単点取得にも対応できます。

template<typename T>
class BIT {
    vector<T> tree;
    int n;
public:
    BIT(int n) : n(n), tree(n + 1, 0) {}
    
    void add(int i, T delta) {
        for (; i <= n; i += i & -i) tree[i] += delta;
    }

    T prefix_sum(int i) {
        T sum = 0;
        for (; i > 0; i -= i & -i) sum += tree[i];
        return sum;
    }
    
    // 差分配列アプローチによる区間加算・単点検索
    void range_add(int l, int r, T delta) {
        add(l, delta);
        add(r + 1, -delta);
    }
    
    T point_query(int i) {
        return prefix_sum(i);
    }
};