概要

この問題は、与えられた学生たちの専門スコア \(W_i\) をもとに、「最大公約数（\(\gcd\)）が \(K\) 以上」という条件で学生同士を繋ぎ、得られる連結成分（グループ）の中で、スコアの総和が最大となるものを求める問題です。

考察

素直なアプローチの問題点

最も単純な方法は、すべての学生のペア \((i, j)\) について \(\gcd(W_i, W_j) \ge K\) であるかを判定し、条件を満たすペアの間に辺を張ったグラフを作成して連結成分を探索することです。 しかし、学生の数 \(N\) は最大で \(2 \times 10^5\) であるため、全ペアを調べると \(O(N^2)\) の計算量となり、実行時間制限に間に合いません（TLE）。

効率化のための重要な気づき

1. スコアが \(K\) 未満の学生

スコア \(W_i\) が \(K\) 未満の学生 \(i\) は、他のどの学生 \(j\) に対しても、最大公約数 \(\gcd(W_i, W_j) \le W_i < K\) となるため、誰とも協力することができません。 したがって、これらの学生は必ず「自分1人だけのグループ」になります。この場合のグループの総合力は \(W_i\) そのものとなるため、あらかじめ \(W_i < K\) である学生のスコアの最大値を保持しておけば十分です。

2. スコアが \(K\) 以上の学生の連結性

スコアが \(K\) 以上の学生たちについて考えます。 2つのスコア \(x, y \ge K\) が共通の約数 \(g \ge K\) を持つとき（すなわち、 \(x\) も \(y\) も \(g\) の倍数であるとき）、最大公約数 \(\gcd(x, y)\) は必ず \(g\) 以上になります。 $\(\gcd(x, y) \ge g \ge K\)\( したがって、**「共通の公約数 \)g \ge K$ を持つスコア同士は、直接協力可能（＝同じグループ）である」**と言えます。

スコアの最大値を \(M\) （ \(M \le 10^6\) ）とすると、各 \(g \ge K\) について、存在する \(g\) の倍数同士をグループとしてマージ（結合）していけば、正しくグループ分けを行うことができます。

アルゴリズム

この問題は、Union-Find（素集合データ構造）と調和級数の性質を利用して高速に解くことができます。

1. スコアの分類と集計

   • \(W_i < K\) の学生のスコアの最大値 max_less_than_K を記録します。
   • \(W_i \ge K\) の学生について、スコアごとの出現回数 count と、スコアの総和 sum_W を集計します（同じスコアの学生は必ず同じグループになるため、まとめて扱います）。

2. Union-Find の初期化

   • \(0\) から \(M\) までの要素を持つ Union-Find を作成します。
   • 各要素 \(x\) の初期の重み（グループの総合力）を sum_W[x] に設定します。

3. 倍数のマージ（結合）

   • 公約数候補 \(g\) を \(K\) から \(M\) までループさせます。
   • 各 \(g\) について、その倍数 \(x = g, 2g, 3g, \ldots \le M\) を探索します。
   • 存在するスコア（count[x] > 0）を最初に見つけたとき、それを first とします。以降に見つかった存在するスコア \(x\) を、Union-Find 上で first と結合（unite）します。結合する際、グループの重み（スコアの総和）も合算します。

4. 最大値の取得

   • \(K\) 以上のすべてのスコアについて、Union-Find 上でのグループの重みの最大値 max_ge_K を求めます。
   • 最終的な答えは、 max(max_less_than_K, max_ge_K) となります。

計算量

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

  • データの入力と集計に \(O(N)\) かかります。
  • 倍数のマージ部分におけるループ回数は、調和級数の和の性質から以下のようになります。 $\(\sum_{g=K}^{M} \frac{M}{g} \approx M \log \left(\frac{M}{K}\right)\)\( \)M \le 10^6\( のとき、この値は高々数百万回であり、Union-Find の操作（ほぼ \)O(1)$）と合わせても実行時間制限に余裕で間に合います。

• 空間計算量: \(O(M)\)

  • スコアの最大値 \(M\) までの情報を格納する配列（count, sum_W）および Union-Find の配列を保持するため、空間計算量は \(O(M)\) となります。

実装のポイント

• Union-Find に重みを持たせる

  • 通常の Union-Find に加え、各グループの「スコアの総和」を管理する配列 weight を持たせています。
  • unite(x, y) を行う際、根の重みを weight[ry] += weight[rx] のように足し合わせることで、グループが結合されたときの総合力を正しく、かつ高速に更新できます。

• 同じスコアのまとめ処理

  • 同じスコアを持つ学生が複数人いる場合、それらを個別に Union-Find で扱うと要素数が \(N\) になり非効率です。スコアの値そのものを Union-Find の要素とし、あらかじめ重みを合計しておくことで、要素数を最大でも \(M \le 10^6\) に抑えることができます。

    ソースコード

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

using namespace std;

struct UnionFind {
    vector<int> parent;
    vector<long long> weight;
    UnionFind(int n, const vector<long long>& init_weight) {
        parent.resize(n);
        iota(parent.begin(), parent.end(), 0);
        weight = init_weight;
    }
    int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }
    void unite(int x, int y) {
        int rx = find(x);
        int ry = find(y);
        if (rx != ry) {
            parent[rx] = ry;
            weight[ry] += weight[rx];
        }
    }
    long long get_weight(int x) {
        return weight[find(x)];
    }
};

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

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

    vector<int> W(N);
    int M = 0;
    long long max_less_than_K = 0;
    for (int i = 0; i < N; ++i) {
        cin >> W[i];
        if (W[i] > M) M = W[i];
        if (W[i] < K) {
            if (W[i] > max_less_than_K) {
                max_less_than_K = W[i];
            }
        }
    }

    vector<long long> sum_W(M + 1, 0);
    vector<int> count(M + 1, 0);
    for (int i = 0; i < N; ++i) {
        if (W[i] >= K) {
            sum_W[W[i]] += W[i];
            count[W[i]]++;
        }
    }

    UnionFind uf(M + 1, sum_W);

    for (int g = K; g <= M; ++g) {
        int first = -1;
        for (int x = g; x <= M; x += g) {
            if (count[x] > 0) {
                if (first == -1) {
                    first = x;
                } else {
                    uf.unite(first, x);
                }
            }
        }
    }

    long long max_ge_K = 0;
    for (int v = K; v <= M; ++v) {
        if (count[v] > 0) {
            max_ge_K = max(max_ge_K, uf.get_weight(v));
        }
    }

    long long ans = max(max_less_than_K, max_ge_K);
    cout << ans << "\n";

    return 0;
}

---

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