概要

参加者を選んでチームを作るとき、チームの「まとまりの良さ」（メンバーのスキルレベルの最大公約数×人数）の最大値を求める問題です。

考察

素朴なアプローチとして、すべての部分集合を試す方法が考えられますが、\(N\) が最大 \(10^6\) なので \(2^N\) 通りを試すことは不可能です。

重要な観察は、最適なチームでは、最大公約数 \(g\) がチーム全員のスキルレベルを割り切るということです。つまり、チームの全メンバーは \(g\) の倍数でなければなりません。

さらに、\(g\) を固定したとき、\(g\) の倍数を持つすべての参加者をチームに含めると、最大公約数が \(g\) 以上になることが保証されます。このときのチームサイズは \(g\) の倍数であるスキルレベルを持つ人数になります。

アルゴリズム

1. 各数値の出現回数をカウントする配列 count を作成
2. 各数 \(g\) について、\(g\) の倍数である数値の出現回数の総和 multiples[g] を計算
3. 各 \(g\) について、まとまりの良さ \(g \times \text{multiples}[g]\) を計算し、最大値を求める

この方法で、すべての可能な \(g\) について効率的に計算できます。\(g\) は \(1\) から最大値までの範囲を調べれば十分です。

計算量

• 時間計算量: \(O(M \log M)\)（\(M\) は入力の最大値）
• 空間計算量: \(O(M)\)

実装のポイント

• 入力の最大値 max_val を求めて、配列のサイズを決定

• 各数値の出現回数をカウントする count 配列を作成

• 二重ループで各 \(g\) の倍数を調べる際、内側のループは \(j = i, 2i, 3i, \ldots\) と飛び飛びにアクセスするため効率的

• 各 \(g\) について、\(g \times \text{multiples}[g]\) を計算して最大値を更新

  ソースコード

import sys
import math

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    A = list(map(int, data[1:1+n]))
    
    max_val = max(A) if A else 0
    count = [0] * (max_val + 1)
    for a in A:
        count[a] += 1
        
    multiples = [0] * (max_val + 1)
    for i in range(1, max_val + 1):
        for j in range(i, max_val + 1, i):
            if count[j] > 0:
                multiples[i] += count[j]
                
    ans = 0
    for g in range(1, max_val + 1):
        if multiples[g] > 0:
            candidate = g * multiples[g]
            if candidate > ans:
                ans = candidate
                
    print(ans)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。