割と簡単にコンテスト当時 2 位水準スコアまで達成したので、方法を書いておきます。

https://atcoder.jp/contests/chokudai002/submissions/20113932

高度合成数のリストアップ

適当なしきい値以上の約数を持つ自然数をリストアップします。

\(\text{MAX} = 10^9\) 以下のすべての自然数について、約数の個数を求めることは、例えばエラストテネスの篩による素因数分解に基づいて \(O(\text{MAX}\log\log \text{MAX})\) 時間でできます。手元実行で数分かけても良いので容易です。

ついでに、これらのリストアップした自然数の約数も列挙しておきます。

貪欲(1)

\(100\) 個の数を順に決めていきます。\(k\) 個の数まで決めたあと、\(k+1\) 個目の数を、その時点でのスコアが最強になるように追加します。（未出の約数の個数が最強のものを選ぶ）

貪欲(2)

例えば貪欲 (1) の解において何度も重複している約数は、例えば貪欲の初手で慌てて選ばなくてもいずれ選ばれると考えました。そこで、貪欲 (1) で \(k\) 回以上出現した約数は評価しないことにして、貪欲 (1) と同じことをします。

パラメータ・スコア

• 高度合成数のリストアップの段階で、約数 \(600\) 個以上の自然数を使うことにしました。全部で \(27402\) 個あります。
• 貪欲 (1) で 42398点
• 貪欲 (2) では、\(k = 3\) を用いました（いくつか試した）。 42820点

はじめ、約数 \(800\) 個以上の高度合成数をもとに同様のアルゴリズムを適用しましたが、40160 点でした。この方針では、ある程度広く高度合成数をリストアップしておく必要がありそうです。