アルゴリズム最適化の基本概念

競技プログラミングにおいて、問題の制約を満たすためには、単純な全探索から数学的な性質や効率的なデータ構造への転換が不可欠です。本記事では、約数とオイラー関数を用いた数論的問題、最長増加部分列（LIS）の個数計算におけるセグメント木の応用、そしてフィボナッチ数列に基づく木構造の動的計画法（DP）について、その数学的背景と計算量削減のアプローチを解説します。

1. オイラー関数と約数を用いた数論的問題

ある整数 $N$ に対し、$1$ から $N$ までの整数のうち平方因子を持つ数が、その最大平方因子の平方根から $1$ を引いた値を寄与するという性質を考えます。単純な列挙では $O(N)$ となりますが、数論的な変形により計算量を大幅に削減できます。

$\gcd(a, b) = d$ と置き、$a = a'd, b = b'd$ （ただし $\gcd(a', b') = 1$）と変形します。条件 $(a'+b')d \mid a'b'd^2$ において、$\gcd(a', b') = 1$ ならば $a'+b'$ は $d$ の約数となります。

$a'+b' = k$ と枚举すると、条件 $(a'+b') \times d \le N$ と $k \mid d$ より、合法的な $d$ の個数は $\lfloor N/k^2 \rfloor$ となります。また、互いに素なペア $(a', b')$ の数はオイラー関数 $\phi(k)$ で求められます。線形篩（エラトステネスの篩の応用）を用いて $\phi$ を前計算することで、効率的に総和を求めることが可能です。

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

const int MAX_LIMIT = 10000005;
vector<int> primes;
vector<int> euler_phi(MAX_LIMIT);
vector<bool> is_composite(MAX_LIMIT);

void compute_euler_totient(int limit) {
    euler_phi[1] = 1;
    for (int i = 2; i <= limit; ++i) {
        if (!is_composite[i]) {
            primes.push_back(i);
            euler_phi[i] = i - 1;
        }
        for (int p : primes) {
            if (i * p > limit) break;
            is_composite[i * p] = true;
            if (i % p == 0) {
                euler_phi[i * p] = euler_phi[i] * p;
                break;
            }
            euler_phi[i * p] = euler_phi[i] * (p - 1);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long n;
    if (!(cin >> n)) return 0;

    int sqrt_n = sqrt(n);
    compute_euler_totient(sqrt_n);

    long long total_sum = 0;
    for (int k = 2; k <= sqrt_n; ++k) {
        total_sum += (long long)euler_phi[k] * (n / ((long long)k * k));
    }

    cout << total_sum << "\n";
    return 0;
}

2. LISの長さと方案数のデータ構造最適化

最長増加部分列（LIS）の長さを求める際、フェニック木（Binary Indexed Tree）を用いると効率的に計算できます。さらに、LISを構成する方案数（パスの数）を求める問題では、動的計画法の状態遷移をセグメント木で最適化します。

セグメント木の各ノードは「区間内の最大値」と「その最大値を取る方案数」を保持します。マージ時には、最大値が等しければ方案数を加算し、異なる場合は大きい方の方案数を採用します。これにより、$O(N \log N)$ でLISの長さだけでなく、その方案数まで求めることが可能になります。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MOD = 123456789;
const int MAX_N = 100005;

int n, task_type;
vector<int> seq(MAX_N), compressed(MAX_N);
vector<int> bit(MAX_N);
vector<int> lis_len(MAX_N);

struct SegNode {
    int max_val;
    long long ways;
};
vector<SegNode> seg_tree(MAX_N * 4);

inline int lowbit(int x) { return x & (-x); }

void bit_update(int idx, int val) {
    for (; idx < MAX_N; idx += lowbit(idx))
        bit[idx] = max(bit[idx], val);
}

int bit_query(int idx) {
    int res = 0;
    for (; idx > 0; idx -= lowbit(idx))
        res = max(res, bit[idx]);
    return res;
}

void push_up(int node) {
    seg_tree[node].max_val = max(seg_tree[node * 2].max_val, seg_tree[node * 2 + 1].max_val);
    if (seg_tree[node * 2].max_val == seg_tree[node * 2 + 1].max_val) {
        seg_tree[node].ways = (seg_tree[node * 2].ways + seg_tree[node * 2 + 1].ways) % MOD;
    } else {
        seg_tree[node].ways = (seg_tree[node * 2].max_val > seg_tree[node * 2 + 1].max_val) 
                              ? seg_tree[node * 2].ways : seg_tree[node * 2 + 1].ways;
    }
}

void seg_update(int node, int l, int r, int pos, int val, long long ways) {
    if (l == r) {
        if (seg_tree[node].max_val == val) {
            seg_tree[node].ways = (seg_tree[node].ways + ways) % MOD;
        } else if (val > seg_tree[node].max_val) {
            seg_tree[node].max_val = val;
            seg_tree[node].ways = ways;
        }
        return;
    }
    int mid = l + (r - l) / 2;
    if (pos <= mid) seg_update(node * 2, l, mid, pos, val, ways);
    else seg_update(node * 2 + 1, mid + 1, r, pos, val, ways);
    push_up(node);
}

pair<int, long long> seg_query(int node, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return {seg_tree[node].max_val, seg_tree[node].ways};
    int mid = l + (r - l) / 2;
    if (qr <= mid) return seg_query(node * 2, l, mid, ql, qr);
    if (ql > mid) return seg_query(node * 2 + 1, mid + 1, r, ql, qr);
    
    auto left_res = seg_query(node * 2, l, mid, ql, qr);
    auto right_res = seg_query(node * 2 + 1, mid + 1, r, ql, qr);
    
    if (left_res.first == right_res.first) 
        return {left_res.first, (left_res.second + right_res.second) % MOD};
    return (left_res.first > right_res.first) ? left_res : right_res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> task_type;
    for (int i = 1; i <= n; ++i) {
        cin >> seq[i];
        compressed[i] = seq[i];
    }

    sort(compressed.begin() + 1, compressed.begin() + n + 1);
    int unique_cnt = unique(compressed.begin() + 1, compressed.begin() + n + 1) - compressed.begin() - 1;

    for (int i = 1; i <= n; ++i) {
        seq[i] = lower_bound(compressed.begin() + 1, compressed.begin() + unique_cnt + 1, seq[i]) - compressed.begin();
    }

    int max_lis = 0;
    for (int i = 1; i <= n; ++i) {
        lis_len[i] = bit_query(seq[i]) + 1;
        bit_update(seq[i] + 1, lis_len[i]);
        max_lis = max(max_lis, lis_len[i]);
    }

    cout << max_lis << "\n";
    if (task_type == 0) return 0;

    seg_update(1, 1, unique_cnt + 1, seq[1] + 1, 1, 1);
    vector<long long> ways(MAX_N, 0);
    
    for (int i = 2; i <= n; ++i) {
        auto res = seg_query(1, 1, unique_cnt + 1, 1, seq[i]);
        ways[i] = max(1LL, res.second % MOD);
        seg_update(1, 1, unique_cnt + 1, seq[i] + 1, lis_len[i], ways[i]);
    }

    long long total_ways = 0;
    for (int i = 1; i <= n; ++i) {
        if (lis_len[i] == max_lis) {
            total_ways = (total_ways + ways[i]) % MOD;
        }
    }
    cout << total_ways << "\n";

    return 0;
}

3. 木構造とフィボナッチ数列に基づくDP

特定の木構造において、各層のノード数がフィボナッチ数列に従う性質を利用します。頂点を黒と白に分類し、それぞれの部分木が全体に与える寄与を独立に計算します。

白ノードを根とする部分木は単純な層ごとの計算で済みますが、黒ノードの場合は「根に直接接続する白ノード」と「それ以外の白ノード」の2パターンに分類する必要があります。後者のパターンは、左右の部分木の深さを枚举することでフィボナッチ数列の畳み込みとして定式化できます。

3重ループの $O(N^3)$ 解法から、配列の累積和やDPテーブルの事前計算を用いることで $O(N^2)$ への最適化を図ります。これにより、大規模な制約下でも十分に高速に動作するアルゴリズムを構築できます。

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 123456789;
const int MAX_N = 10005;

int n;
vector<long long> fib(MAX_N);
vector<long long> ans(MAX_N * 2);
vector<vector<long long>> dp_table(MAX_N, vector<long long>(MAX_N * 2, 0));

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    
    fib[1] = fib[2] = 1;
    for (int i = 3; i <= n; ++i) {
        fib[i] = (fib[i - 1] + fib[i - 2]) % MOD;
    }

    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j <= 2 * n; ++j) {
            dp_table[i][j] = (dp_table[i][j] + dp_table[i - 1][j]) % MOD;
        }
        for (int j = 3; j <= n; ++j) {
            int max_idx = max(i, j);
            int sum_idx = i + j;
            dp_table[max_idx][sum_idx] = (dp_table[max_idx][sum_idx] + fib[i - 1] * fib[j - 2] % MOD) % MOD;
        }
    }

    for (int i = 2; i <= n; ++i) {
        for (int j = 5; j <= 2 * (n - i); ++j) {
            ans[j] = (ans[j] + dp_table[n - i][j] * fib[i - 1] % MOD) % MOD;
        }
        for (int j = i + 2; j <= n; ++j) {
            ans[j - i + 1] = (ans[j - i + 1] + fib[i - 1] * fib[j - i - 1] % MOD) % MOD;
        }
        for (int j = i + 1; j < n; ++j) {
            ans[j - i + 1] = (ans[j - i + 1] + fib[i - 2] * fib[j - i] % MOD) % MOD;
        }
    }

    for (int i = 3; i <= n; ++i) {
        ans[i - 1] = (ans[i - 1] + fib[i - 2]) % MOD;
    }

    for (int i = 1; i <= 2 * n; ++i) {
        cout << ans[i] << (i == 2 * n ? "" : " ");
    }
    cout << "\n";

    return 0;
}