高精度計算

トライ木を用いたA+B

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;

struct TrieNode {
    int children[26];
    int value;
} nodes[1000];

char buffer[100];
int nodeCount = 0, totalNodes = 0, resultSum = 0;
bool negativeFlag;

void insertNumber() {
    int current = 0;
    for (int i = 0; buffer[i] != '\0'; i++) {
        if (buffer[i] == '-') {
            negativeFlag = true;
            continue;
        }
        int digit = buffer[i] - '0';
        if (nodes[current].children[digit] == 0)
            nodes[current].children[digit] = ++totalNodes;
        current = nodes[current].children[digit];
        nodes[current].value = digit;
    }
}

int queryNumber() {
    int current = 0, result = 0;
    for (int i = 0; buffer[i] != '\0'; i++) {
        if (buffer[i] == '-') continue;
        int digit = buffer[i] - '0';
        if (nodes[current].children[digit] == 0) return result;
        current = nodes[current].children[digit];
        result = result * 10 + nodes[current].value;
    }
    return result;
}

int main() {
    for (int i = 1; i <= 2; i++) {
        negativeFlag = false;
        scanf("%s", buffer);
        insertNumber();
        if (negativeFlag)
            resultSum -= queryNumber();
        else
            resultSum += queryNumber();
    }
    printf("%d\n", resultSum);
    return 0;
}

筆算によるA+B (文字列処理)

#include <string>
#include <iostream>
using namespace std;

int numA[100], numB[100], result[100];
int lenA, lenB, resultLen = 1;

int main() {
    string strA, strB;
    cin >> strA >> strB;
    lenA = strA.length();
    lenB = strB.length();
    for (int i = 1; i <= lenA; i++) numA[i] = strA[lenA - i] - 48;
    for (int i = 1; i <= lenB; i++) numB[i] = strB[lenB - i] - 48;
    int carry = 0;
    while (resultLen <= lenA || resultLen <= lenB) {
        result[resultLen] = numA[resultLen] + numB[resultLen] + carry;
        carry = result[resultLen] / 10;
        result[resultLen] %= 10;
        resultLen++;
    }
    result[resultLen] = carry;
    if (result[resultLen] == 0) resultLen--;
    for (int i = resultLen; i > 0; i--) cout << result[i];
    return 0;
}

A×B (簡易高精度)

基本データ構造

便利なマクロとUtility

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

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))

inline int fastRead() {
    int f = 1, x = 0;
    char ch;
    do { ch = getchar(); if (ch == '-') f = -1; } while (ch < '0' || ch > '9');
    do { x = x * 10 + ch - '0'; ch = getchar(); } while (ch >= '0' && ch <= '9');
    return f * x;
}

inline void fastPrint(int x) {
    if (x < 0) { putchar('-'); fastPrint(-x); return; }
    if (x >= 10) fastPrint(x / 10);
    putchar(x % 10 + '0');
}

// 疑似128ビット整数 (long long 2つ組み合わせ)
using ll = long long;
const ll BASE = 1e9;
struct BigInt {
    ll low, high;
    BigInt() : low(0), high(0) {}
    BigInt(ll v) { low = v % BASE; high = v / BASE; }
    friend BigInt operator+(const BigInt &a, const BigInt &b) {
        BigInt c;
        c.low = a.low + b.low;
        c.high = a.high + b.high;
        if (c.low < 0 && c.high > 0) { c.high--; c.low += BASE; }
        if (c.low >= BASE) { c.high += c.low / BASE; c.low %= BASE; }
        return c;
    }
    friend bool operator<(const BigInt &a, const BigInt &b) {
        if (a.high != b.high) return a.high < b.high;
        return a.low < b.low;
    }
};

// cin高速化
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

リンクリスト

struct Node {
    Node *prev, *next;
    int data;
    Node(int d) : prev(nullptr), next(nullptr), data(d) {}
};

void insertAfter(Node *x, Node *y) {
    if (x->next) {
        y->next = x->next;
        y->next->prev = y;
    }
    x->next = y;
    y->prev = x;
}

void removeNode(Node *x) {
    if (x->prev) x->prev->next = x->next;
    if (x->next) x->next->prev = x->prev;
    delete x;
}

スタックとキュー (配列実装)

struct MyStack {
    int data[100010];
    int top;
    MyStack() : top(0) {}
    void push(int x) { data[++top] = x; }
    void pop() { if (top) top--; }
    int size() { return top; }
    int query() { return data[top]; }
};

struct MyQueue {
    int data[100010];
    int front, rear;
    MyQueue() : front(0), rear(0) {}
    void push(int x) {
        if (rear == 100000) rear = 1; else rear++;
        data[rear] = x;
    }
    void pop() {
        if (front == 100000) front = 1; else front++;
    }
    int getFront() { return data[front]; }
    int size() {
        if (front < rear) return rear - front;
        else return front - rear + 1;
    }
    bool empty() { return front == rear; }
};

単調キュー (Min/Max スライド窓)

#include <stdio.h>
const int N = 1000000 + 10;

inline int read() {
    int x = 0, f = 1; char ch;
    do { ch = getchar(); if (ch == 45) f = -1; } while (ch < 48 || ch > 57);
    do { x = x * 10 + ch - 48; ch = getchar(); } while (ch >= 48 && ch <= 57);
    return f * x;
}

struct SlidingWindow {
    int values[N], indices[N];
    int l, r;
    void init() { l = 0; r = -1; }
    void push(int idx, int val) {
        while (l <= r && values[r] >= val) r--;
        values[++r] = val;
        indices[r] = idx;
    }
    int getMin(int idx, int k) {
        while (l <= r && idx - indices[l] >= k) l++;
        return values[l];
    }
} w;

void slideMin(int a[], int n, int k) {
    w.init();
    for (int i = 0; i < n; i++) {
        w.push(i, a[i]);
        if (i >= k - 1) printf("%d ", w.getMin(i, k));
    }
    printf("\n");
}

優先度付きキュー (ヒープ)

#include <queue>
using namespace std;
priority_queue<int> maxHeap;                         // 最大値
priority_queue<int, vector<int>, greater<int>> minHeap; // 最小値

文字列ハッシュ

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
using ull = unsigned long long;

const ull BASE = 131;
const ull MOD = 212370440130137957ull;
const ull PRIME = 233317;
ull hashVal[10010];
char buf[10010];

ull hashStr(char s[]) {
    int len = strlen(s);
    ull res = 0;
    for (int i = 0; i < len; i++)
        res = (res * BASE + (ull)s[i]) % MOD + PRIME;
    return res;
}

int main() {
    int n; scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s", buf);
        hashVal[i] = hashStr(buf);
    }
    sort(hashVal, hashVal + n);
    int ans = 1;
    for (int i = 1; i < n; i++)
        if (hashVal[i] != hashVal[i-1]) ans++;
    printf("%d\n", ans);
    return 0;
}

トライ (Trie)

#include <cstdio>
#include <cstring>

int trie[1000010][62], cnt[1000010], idx;
char str[10010];

int charIndex(char c) {
    if (c >= 'A' && c <= 'Z') return c - 'A';
    if (c >= 'a' && c <= 'z') return c - 'a' + 26;
    return c - '0' + 52;
}

void insert(char s[]) {
    int p = 0, len = strlen(s);
    for (int i = 0; i < len; i++) {
        int c = charIndex(s[i]);
        if (!trie[p][c]) trie[p][c] = ++idx;
        p = trie[p][c];
        cnt[p]++;
    }
}

int query(char s[]) {
    int p = 0, len = strlen(s);
    for (int i = 0; i < len; i++) {
        int c = charIndex(s[i]);
        if (!trie[p][c]) return 0;
        p = trie[p][c];
    }
    return cnt[p];
}

グラフと木

グラフの保存

連鎖前方型 (Chain Forward Star)

struct Edge {
    int to, next, w;
} edges[1000000];
int head[1000000], edgeCount = 0;

void addEdge(int u, int v, int w = 0) {
    edges[++edgeCount].to = v;
    edges[edgeCount].w = w;
    edges[edgeCount].next = head[u];
    head[u] = edgeCount;
}

単一始点最短路

Floyd-Warshall

#include <bits/stdc++.h>
using namespace std;
#define INF 123456789
int dist[10005][10005], n, m, s;

void floyd() {
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++) {
            if (i == k || dist[i][k] == INF) continue;
            for (int j = 1; j <= n; j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        }
}

SPFA (Bellman-Ford 改良版)

#include <queue>
#include <cstdio>
const int N = 10005, M = 500005, INF = 1e9;
int head[N], n, m, s;
struct Edge { int to, next, w; } ed[M];
int dis[N]; bool vis[N];

void spfa() {
    for (int i = 1; i <= n; i++) dis[i] = INF;
    dis[s] = 0;
    queue<int> q; q.push(s); vis[s] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop(); vis[u] = false;
        for (int i = head[u]; i; i = ed[i].next) {
            int v = ed[i].to;
            if (dis[u] + ed[i].w < dis[v]) {
                dis[v] = dis[u] + ed[i].w;
                if (!vis[v]) { vis[v] = true; q.push(v); }
            }
        }
    }
}

ダイクストラ (優先度付きキュー最適化)

#include <queue>
#include <cstdio>
using namespace std;
const int N = 100005, INF = 2147483647;
int head[N], cnt;
struct Edge { int to, next, w; } e[N];
int dis[N]; bool vis[N];

struct Node {
    int dist, idx;
    bool operator<(const Node &other) const { return dist > other.dist; }
};

void dijkstra(int s) {
    for (int i = 1; i <= N; i++) dis[i] = INF;
    dis[s] = 0;
    priority_queue<Node> pq;
    pq.push({0, s});
    while (!pq.empty()) {
        Node cur = pq.top(); pq.pop();
        int u = cur.idx;
        if (vis[u]) continue;
        vis[u] = true;
        for (int i = head[u]; i; i = e[i].next) {
            int v = e[i].to;
            if (dis[v] > dis[u] + e[i].w) {
                dis[v] = dis[u] + e[i].w;
                pq.push({dis[v], v});
            }
        }
    }
}

トポロジカルソート

最小全域木

クラスカル法

木の直径と重心

LCA (最近共通祖先)

動的計画法 (DP)

線形DP

最長増加部分列 (LIS)

#include <algorithm>
using namespace std;
int a[100], dp[100], n;
int lis() {
    int ans = 0;
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++)
            if (a[i] > a[j]) dp[i] = max(dp[i], dp[j] + 1);
        ans = max(ans, dp[i]);
    }
    return ans;
}

最長共通部分列 (LCS)

int lcs(char *A, char *B, int n, int m) {
    int dp[100][100] = {};
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (A[i-1] == B[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[n][m];
}

ナップザックDP

01 ナップザック

int weight[50010], value[50010], dp[50010];
int n, capacity;
int main() {
    cin >> n >> capacity;
    for (int i = 1; i <= n; i++) cin >> weight[i] >> value[i];
    for (int i = 1; i <= n; i++)
        for (int j = capacity; j >= weight[i]; j--)
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    cout << dp[capacity];
}

完全ナップザック (個数制限なし)

int n, capacity;
int w, v, dp[50010];
int main() {
    scanf("%d%d", &n, &capacity);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &w, &v);
        for (int j = w; j <= capacity; j++)
            dp[j] = max(dp[j], dp[j - w] + v);
    }
    printf("%d", dp[capacity]);
}

グループナップザック

int dp[50010], group[10010][10010], count[10010];
int main() {
    int capacity, n; cin >> capacity >> n;
    int w, v, g, maxGroup = 0;
    for (int i = 1; i <= n; i++) {
        cin >> w >> v >> g;
        maxGroup = max(maxGroup, g);
        count[g]++;
        group[g][count[g]] = i; // インデックスを保存
    }
    for (int g = 1; g <= maxGroup; g++)
        for (int j = capacity; j >= 0; j--)
            for (int k = 1; k <= count[g]; k++) {
                // 実際の重みと価値は別途配列で持つ
            }
}

探索 (Search)

深さ優先探索 (DFS) - 例：n-Queen

int n, ans, col[20], diag1[40], diag2[40];
void search(int y) {
    if (y == n) { ans++; return; }
    for (int x = 0; x < n; x++) {
        if (col[x] || diag1[x+y] || diag2[x-y+n-1]) continue;
        col[x] = diag1[x+y] = diag2[x-y+n-1] = 1;
        search(y+1);
        col[x] = diag1[x+y] = diag2[x-y+n-1] = 0;
    }
}

幅優先探索 (BFS) - 例：迷路の最短距離

#include <queue>
#include <utility>
using namespace std;
int maze[100][100], dist[100][100];
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
int h, w;

void bfs(int sx, int sy) {
    queue<pair<int,int>> q;
    q.push({sx, sy});
    dist[sx][sy] = 0;
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k], ny = y + dy[k];
            if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
            if (maze[nx][ny] == 1 || dist[nx][ny] != -1) continue;
            dist[nx][ny] = dist[x][y] + 1;
            q.push({nx, ny});
        }
    }
}

二分探索と貪欲法

二分探索 (一般的な実数値探索)

double findRoot(double l, double r, double eps) {
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (f(mid) == 0) return mid;
        if (f(l) * f(mid) < 0) r = mid;
        else l = mid;
    }
    return l;
}

STL二分探索

#include <algorithm>
#include <vector>
using namespace std;
vector<int> v = {1, 3, 5, 7, 9};
auto it = lower_bound(v.begin(), v.end(), 5); // 最初の5以上の要素
size_t idx = it - v.begin();

数学

素数関連

試し割りによる判定

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) return false;
    return true;
}

エラトステネスの篩

bool isComposite[100000001];
int primes[20000001], pcnt;
void sieve(int n) {
    for (int i = 2; i <= n; i++) {
        if (!isComposite[i]) primes[++pcnt] = i;
        for (int j = 1; j <= pcnt && i * primes[j] <= n; j++) {
            isComposite[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

GCD & LCM

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

高速累乗 (繰り返し二乗法)

int fastPow(int a, int b, int mod) {
    int res = 1;
    while (b > 0) {
        if (b & 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}

行列累乗 (フィボナッチ数列)

struct Mat {
    long long m[2][2];
    Mat() { memset(m, 0, sizeof(m)); }
    Mat operator*(const Mat &b) const {
        Mat c;
        for (int i = 0; i < 2; i++)
            for (int k = 0; k < 2; k++)
                for (int j = 0; j < 2; j++)
                    c.m[i][j] = (c.m[i][j] + m[i][k] * b.m[k][j]) % MOD;
        return c;
    }
};

Mat matPow(Mat a, long long n) {
    Mat res; res.m[0][0] = res.m[1][1] = 1;
    while (n) {
        if (n & 1) res = res * a;
        a = a * a;
        n >>= 1;
    }
    return res;
}

その他頻出テクニック

累積和 (Prefix Sum)

long long arr[100005], prefix[100005];
int n;
for (int i = 1; i <= n; i++) prefix[i] = prefix[i - 1] + arr[i];
// [l, r] 区間和 = prefix[r] - prefix[l-1]

差分 (Difference Array)

long long diff[100005];
void addRange(int l, int r, long long val) {
    diff[l] += val;
    diff[r + 1] -= val;
}
// 戻し方: for (int i = 1; i <= n; i++) arr[i] = arr[i-1] + diff[i];

Union-Find (Disjoint Set Union)

int parent[100010];
int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
void unite(int x, int y) { parent[find(x)] = find(y); }
int main() {
    int n, m; scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) parent[i] = i;
    while (m--) {
        int op, x, y; scanf("%d%d%d", &op, &x, &y);
        if (op == 1) unite(x, y);
        else puts(find(x) == find(y) ? "Y" : "N");
    }
}

KMP (文字列検索)

#include <iostream>
#include <cstring>
using namespace std;
char text[1000010], pattern[1000010];
int lps[1000010];

int main() {
    cin >> text+1 >> pattern+1;
    int n = strlen(text+1), m = strlen(pattern+1);
    // LPS テーブル構築
    lps[1] = 0;
    for (int i = 2, len = 0; i <= m; i++) {
        while (len > 0 && pattern[i] != pattern[len+1]) len = lps[len];
        if (pattern[i] == pattern[len+1]) len++;
        lps[i] = len;
    }
    // マッチング
    for (int i = 1, j = 0; i <= n; i++) {
        while (j > 0 && text[i] != pattern[j+1]) j = lps[j];
        if (text[i] == pattern[j+1]) j++;
        if (j == m) {
            cout << i - m + 1 << endl;
            j = lps[j];
        }
    }
}

K番目の要素 (std::nth_element)

#include <algorithm>
#include <vector>
vector<int> v = {3, 1, 4, 1, 5, 9, 2};
nth_element(v.begin(), v.begin() + 2, v.end()); // 3番目 (0-indexed) が確定
// v[2] が小さい方から3番目になる