公式

E - ネットワークの巡回点検 / Network Patrol Inspection 解説 by admin

gemini-3.5-flash-high(計算量の説明が誤り)

概要

この問題は、与えられたルールに従って \(1\) から \(N\) までのサーバーを巡回するシミュレーションを行い、巡回を開始した総回数を求める問題です。

素朴にシミュレーションを行うと、「次に移動できる、共通の素因数を持つ最小の未点検サーバー」を探す部分に時間がかかってしまいます。この探索を高速化するために、Union-Find (DSU) を応用した効率的なスキップアルゴリズムを設計する必要があります。

考察

素朴なシミュレーションの限界

現在地を \(k\) としたとき、次の移動先は「\(k\) と共通の素因数 \(p\) を持つ、 \(k\) より大きい最小の未点検サーバー \(m\)」です。

これを探すために、 \(k\) の各素因数 \(p\) について、 \(k\) より大きい \(p\) の倍数（\(k+p, k+2p, \dots\)）を愚直に走査して未点検のものを探すとします。しかし、すでに多くのサーバーが点検済みである場合、未点検のサーバーにたどり着くまでに大量の「点検済みサーバー」をスキップすることになります。 最悪の場合、この走査に \(O(N)\) の時間がかかってしまい、全体の計算量が \(O(N^2)\) となって実行時間制限（TLE）に間に合いません。

高速化のアイデア：Union-Find によるスキップ

「すでに点検済みのサーバーを高速にスキップする」ために、Union-Find を活用します。

各素数 \(p\) について、「\(p\) の倍数」だけを管理する独立した Union-Find を用意します。 \(p\) の倍数 \(x \cdot p\) が点検済みになったとき、Union-Find 上でインデックス \(x\) と \(x+1\) を連結（マージ）します。

具体例：\(p = 3\) の場合

\(3\) の倍数 \(3, 6, 9, 12, 15, \dots\) を、それぞれインデックス \(x = 1, 2, 3, 4, 5, \dots\) で管理します。

  1. 初期状態: すべて未点検です。
    • Union-Find の代表元: [1, 2, 3, 4, 5, ...]
  2. \(6\) (\(x=2\)) が点検される:
    • \(x=2\) と \(x=3\) をマージします。
    • Union-Find の代表元: [1, 3, 3, 4, 5, ...] （\(2\) の親が \(3\) になります）
    • このとき、次に \(6\) より大きい \(3\) の倍数を探すには、find(2 + 1) = find(3) = 3 となり、\(9\) (\(x=3\)) が次の候補であると一瞬でわかります。
  3. \(9\) (\(x=3\)) も点検される:
    • \(x=3\) と \(x=4\) をマージします。
    • Union-Find の代表元: [1, 4, 4, 4, 5, ...]
    • この状態で、再び「\(6\) より大きい最小の \(3\) の倍数」を探すと、find(2 + 1) = find(3) = 4 となり、すでに点検済みの \(9\) をスキップして \(12\) (\(x=4\)) を直接見つけることができます。

このように、Union-Find の find 操作（経路圧縮あり）を用いることで、点検済みの要素を \(O(\alpha(N))\) のほぼ定数時間でスキップできます。

アルゴリズム

1. 事前準備

  1. SPF (Smallest Prime Factor) の計算: エラトステネスの篩の要領で、各数 \(i\) の最小の素因数を求めておきます。これにより、任意の数 \(i\) の素因数分解を \(O(\log i)\) で高速に行えるようになります。
  2. 素因数リストの構築: 各数 \(i \in [2, N]\) のユニークな素因数リストを事前に作成しておきます。
  3. 素数の列挙と Union-Find の初期化: \(N\) 以下の素数 \(p\) を列挙し、それぞれに ID を割り当てます。 各素数 \(p\) に対して、サイズ \(\lfloor N/p \rfloor + 2\) の Union-Find を構築します。

2. シミュレーション

未点検の最小のサーバーの番号を指す変数 min_unvisited を \(1\) としておきます。

min_unvisited <= N である限り、以下の手順を繰り返します。

  1. 新たな巡回の開始:

    • min_unvisited がすでに訪問済みなら、min_unvisited を \(1\) 進めてスキップします。
    • 未点検であれば、巡回回数 ans を \(+1\) し、現在地 \(k = min\_unvisited\) とします。
    • \(k\) を訪問済みにし、 \(k\) の各素因数 \(p\) について、 \(p\) の Union-Find で \(k/p\) と \(k/p + 1\) をマージします。

  2. 巡回中の移動:

    • \(k = 1\) の場合:
      • min_unvisited を進めて、最初に見つかった未点検のサーバーを次の移動先 \(next\_m\) とします。
    • \(k \ge 2\) の場合:
      • \(k\) の各素因数 \(p\) について、 \(p\) の Union-Find で find(k/p + 1) を計算し、次の未点検候補のインデックス \(next\_idx\) を得ます。
      • 候補となる値 \(next\_idx \cdot p\) のうち、 \(N\) 以下で最小のものを次の移動先 \(next\_m\) とします。
    • \(next\_m\) が存在しない（\(N\) を超える）場合、この巡回を終了して手順 1 に戻ります。
    • 存在する場合、 \(k = next\_m\) に移動し、 \(k\) を訪問済みに更新し、各素因数 \(p\) について \(k/p\) と \(k/p + 1\) をマージして移動を繰り返します。

計算量

時間計算量: \(O(N \log \log N)\)

  • SPF の構築: \(O(N \log \log N)\) です。
  • 素因数リストの構築: 各数 \(i\) の素因数の個数は、 \(N \le 5 \times 10^5\) において高々 \(7\) 個（\(2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 > 5 \times 10^5\) であるため）です。したがって、全体で \(O(N)\) 程度の計算量です。
  • Union-Find の初期化: 各素数 \(p\) に対する要素数の合計は \(\sum_{p \le N} \frac{N}{p} = O(N \log \log N)\) です。
  • シミュレーション: 各サーバーは高々 \(1\) 回しか訪問されず、訪問時に行う Union-Find の操作回数はその数の素因数の個数（高々 \(7\) 回）に比例します。Union-Find の操作はほぼ定数時間 \(O(\alpha(N))\) なので、全体で \(O(N \alpha(N))\) です。

以上より、全体の時間計算量は \(O(N \log \log N)\) となり、制限時間内に余裕で間に合います。

空間計算量: \(O(N \log \log N)\)

  • 各数の素因数リスト、および Union-Find の全ノード数の合計は、ともに \(O(N \log \log N)\)（または実質的に \(O(N)\)）であり、メモリ制限（通常 1024MB など）に対して数十MB 程度に収まります。

実装のポイント

  • メモリのフラット化（高速化）: C++ で vector<vector<int>> を多用すると、メモリの動的確保のオーバーヘッドやキャッシュミスの原因になります。 提示されたコードでは、2次元的なデータ（各数の素因数リストや、素数ごとの Union-Find 配列）を、1次元配列（factor_list や dsu_parent）とそれぞれの開始位置を指すオフセット配列（factor_offset や dsu_offset）を用いて平坦化（フラット化）して管理しています。これにより、実行速度とメモリ効率が極限まで高められています。

    ソースコード

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <span>

using namespace std;

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

    int N;
    if (!(cin >> N)) return 0;

    if (N == 1) {
        cout << 1 << "\n";
        return 0;
    }

    // SPF (Smallest Prime Factor) calculation
    vector<int> spf(N + 1);
    iota(spf.begin(), spf.end(), 0);
    for (int i = 2; i * i <= N; ++i) {
        if (spf[i] == i) {
            for (int j = i * i; j <= N; j += i) {
                if (spf[j] == j) spf[j] = i;
            }
        }
    }

    // Prime factorization list flattening
    vector<int> factor_offset(N + 2, 0);
    for (int i = 2; i <= N; ++i) {
        int temp = i;
        while (temp > 1) {
            int p = spf[temp];
            factor_offset[i + 1]++;
            while (temp % p == 0) temp /= p;
        }
    }
    for (int i = 2; i <= N + 1; ++i) {
        factor_offset[i] += factor_offset[i - 1];
    }
    vector<int> factor_list(factor_offset[N + 1]);
    vector<int> factor_cur = factor_offset;
    for (int i = 2; i <= N; ++i) {
        int temp = i;
        while (temp > 1) {
            int p = spf[temp];
            factor_list[factor_cur[i]++] = p;
            while (temp % p == 0) temp /= p;
        }
    }

    auto get_factors = [&](int i) {
        return std::span<const int>(factor_list.data() + factor_offset[i], factor_list.data() + factor_offset[i + 1]);
    };

    // Primes list and mapping
    vector<int> primes;
    vector<int> prime_to_id(N + 1, -1);
    vector<bool> is_prime(N + 1, true);
    is_prime[0] = is_prime[1] = false;
    int p_id = 0;
    for (int p = 2; p <= N; ++p) {
        if (is_prime[p]) {
            primes.push_back(p);
            prime_to_id[p] = p_id++;
            for (int j = 2 * p; j <= N; j += p) {
                is_prime[j] = false;
            }
        }
    }

    int num_primes = primes.size();
    vector<int> dsu_offset(num_primes + 1, 0);
    for (int i = 0; i < num_primes; ++i) {
        int p = primes[i];
        int size = N / p + 2;
        dsu_offset[i + 1] = dsu_offset[i] + size;
    }
    int total_dsu_size = dsu_offset[num_primes];
    vector<int> dsu_parent(total_dsu_size);
    for (int i = 0; i < num_primes; ++i) {
        int offset = dsu_offset[i];
        int size = N / primes[i] + 2;
        for (int j = 0; j < size; ++j) {
            dsu_parent[offset + j] = j;
        }
    }

    auto find = [&](int p_id, int i) -> int {
        int offset = dsu_offset[p_id];
        int curr = i;
        while (dsu_parent[offset + curr] != curr) {
            curr = dsu_parent[offset + curr];
        }
        int temp = i;
        while (temp != curr) {
            int next = dsu_parent[offset + temp];
            dsu_parent[offset + temp] = curr;
            temp = next;
        }
        return curr;
    };

    auto merge = [&](int p_id, int i, int j) {
        int root_i = find(p_id, i);
        int root_j = find(p_id, j);
        if (root_i != root_j) {
            dsu_parent[dsu_offset[p_id] + root_i] = root_j;
        }
    };

    vector<bool> visited(N + 1, false);
    int ans = 0;
    int min_unvisited = 1;

    while (min_unvisited <= N) {
        if (visited[min_unvisited]) {
            min_unvisited++;
            continue;
        }

        ans++;
        int k = min_unvisited;
        visited[k] = true;
        for (int p : get_factors(k)) {
            int pid = prime_to_id[p];
            merge(pid, k / p, k / p + 1);
        }

        while (true) {
            int next_m = N + 1;
            if (k == 1) {
                while (min_unvisited <= N && visited[min_unvisited]) {
                    min_unvisited++;
                }
                if (min_unvisited <= N) {
                    next_m = min_unvisited;
                }
            } else {
                for (int p : get_factors(k)) {
                    int pid = prime_to_id[p];
                    int start_idx = k / p + 1;
                    int next_idx = find(pid, start_idx);
                    long long val = (long long)next_idx * p;
                    if (val <= N) {
                        next_m = min(next_m, (int)val);
                    }
                }
            }

            if (next_m > N) {
                break;
            }

            k = next_m;
            visited[k] = true;
            for (int p : get_factors(k)) {
                int pid = prime_to_id[p];
                merge(pid, k / p, k / p + 1);
            }
        }
    }

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

この解説は gemini-3.5-flash-high によって生成されました。

投稿日時:
最終更新: