概要

\(N\) 人の参加者から何人かを選び、「選んだメンバーのスキルレベルの最大公約数 \(\times\) 選んだ人数」を最大化する問題です。

考察

素朴なアプローチではなぜダメか 参加者の選び方は全部で \(2^N - 1\) 通りあります。これを全探索しようとすると、\(N \le 10^6\) という制約では計算に天文学的な時間がかかり、時間切れ（TLE）になってしまいます。

視点を変える：「最大公約数（GCD）」を固定する 選ぶメンバーの組み合わせから考えるのではなく、「チームのGCDを \(g\) にする」と仮定して考えてみましょう。 チームのGCDが \(g\) になるということは、選ばれたメンバー全員のスキルレベルが \(g\) の倍数 である必要があります。

まとまりの良さは「\(g \times\) 人数」で計算されるため、\(g\) を固定したなら、人数は多ければ多いほど良いことになります。 したがって、スキルレベルが \(g\) の倍数である人を全員選ぶのが最適です。

「でも、全員選んだら実際のGCDが \(g\) より大きくなってしまわない？」と疑問に思うかもしれません。 例えば、参加者のスキルレベルが \(A = [4, 8, 12]\) だったとします。\(g=2\) として2の倍数を全員選ぶと、選ばれるのは \(4, 8, 12\) の3人で、実際のGCDは \(4\) になります。 しかし、心配は不要です。なぜなら、その場合は後から \(g=4\) を調べたときに「\(4 \times 3\)」としてより大きな値が正しく計算され、最大値が更新されるからです。 つまり、すべての \(g\) について「\(g \times (A に含まれる g の倍数の個数)\)」を計算し、その最大値をとれば正しい答えが求まります。

アルゴリズム

1. 入力されたスキルレベル \(A_i\) の最大値を \(M\) とします。
2. 各スキルレベルが何人いるかを数え、配列 count に記録します。
3. チームのGCDの候補 \(g\) を \(1\) から \(M\) まで全探索します。
4. 各 \(g\) について、\(A\) の中に \(g\) の倍数が何個あるか（何人いるか）を調べます。 これは count[g] + count[2g] + count[3g] + ... と足し合わせることで求められます。
5. 「\(g \times (g\) の倍数の人数\()\)」を計算し、最大値を更新していきます。
6. 最終的な最大値を出力します。

計算量

• 時間計算量: \(O(N + M \log M)\)
  • \(A_i\) の集計に \(O(N)\) かかります。
  • 倍数のカウント処理の計算回数は、\(\frac{M}{1} + \frac{M}{2} + \frac{M}{3} + \dots + \frac{M}{M}\) となります。これは「調和級数」と呼ばれ、おおよそ \(M \log M\) に比例することが知られています。
  • したがって、全体で \(O(N + M \log M)\) となり、\(N, M \le 10^6\) でも十分に高速に動作します。
• 空間計算量: \(O(N + M)\)
  • 入力データの保持に \(O(N)\)、要素の出現回数を記録する配列 count に \(O(M)\) の空間を使用します。

実装のポイント

Pythonでは単純な for ループを回して倍数を足し合わせると、ループのオーバーヘッドで実行時間が長くなることがあります。 正解コードでは sum(count[g::g]) というリストのスライス機能を活用しています。これを使うと、count 配列からインデックスが \(g\) の倍数である要素だけを内部の最適化された処理で一気に取り出して和を求めることができ、大幅な高速化に繋がります。 また、sys.stdin.read().split() を用いて入力を一括で読み込むことも、大量の入力を扱う競技プログラミングにおける高速化の定石です。

ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    A = [int(x) for x in input_data[1:]]
    
    M = max(A)
    count = [0] * (M + 1)
    for a in A:
        count[a] += 1
        
    ans = 0
    for g in range(1, M + 1):
        c = sum(count[g::g])
        res = c * g
        if res > ans:
            ans = res
            
    print(ans)

if __name__ == '__main__':
    main()

この解説は gemini-3.1-pro-thinking によって生成されました。