バチャをした。
最初のほうに考えたこと:
- 小さい範囲での全探索の結果は、偶数しかない。
- 例えば40があったら20を入れるのは意味なさそうだし、逆に20を入れるなら40を入れるべきという話にはなる。
- 整除関係において極大な数に絞る？
- 整除関係において極大だからといって、素数を入れる意味はなさそう。
- いちばん大きな数の半分以下の数を調べなくてよい。（2倍を入れて損はないので。） とすると、$(5\cdot10^8, 10^9]$を探す感じか。
- $(5\cdot10^8, 10^9]$の中の偶数から探すとすると、$2.5 \times 10^8$個を調べることになる。この程度ならひとつひとつ調べるような方針はありそう。
- ある程度$d(n)$が大きい整数の集合から愚直焼きなまし、はありえる？
そもそも約数の総数はどのくらいが相場だったかか覚えていない。$10^9$から下って$998000000$あたりまで調べてmaxを探す:
1000000000 100個
999999990 192個
999999840 576個
999999000 1024個
998917920 1080個
...
だいたい相場がわかったので、とりあえず約数が600より多い整数を100個見つけて並べると36000。すでにけっこう高い。
約数の数が700以上、で同じことをやる。(37000)
新たに整数を追加した時のスコアの上昇を調べる:
999999000 1024
999989760 576
999959040 552
999949860 720
999936000 468
999915840 454
999853470 488
999835200 522
999814200 540
999782784 469
999760320 463
999758760 576
999734400 601
999702000 420
999697920 388
999694080 506
999657120 466
999638640 582
999621000 372
999567360 323
999566568 369
999532800 320
999511920 454
999507600 395
999500040 440
999488160 360
999447120 388
999398400 392
999383616 315
999375300 464
999371520 278
999350100 354
999311040 440
999306000 409
999295920 404
999278280 528
999266400 312
999223680 340
999217296 356
999187200 354
999180000 444
999167400 304
999159840 434
999129600 335
999114480 423
999076680 296
999028800 486
999016200 420
998917920 378
998899200 337
998891712 298
998875800 252
998857440 332
998856144 274
998844000 374
998820900 312
998811000 273
998808720 324
998786880 309
998776800 344
998749440 220
998712000 356
998692200 292
998688600 272
998686080 343
998634000 228
998612160 312
998609040 350
998600400 295
998585280 460
998565120 279
998557560 408
998549370 238
998529840 331
998524800 393
998497500 252
998490240 260
998457600 270
998418960 329
998382528 228
998373600 276
998361000 333
998300160 273
998298000 339
998289600 268
998265840 270
998243400 282
998197200 361
998150400 210
998147520 241
998086320 321
998071200 301
998038080 285
998000640 224
997978800 238
997956960 296
997949160 216
997920000 218
997908912 239
997883040 222
追加される約数の数がだんだん減っていく。このカーブを適切に決めて、閾値を超えるものだけ取ればよい？
二次回帰して回帰曲線を超えるものだけ取ろうとしたりする。1時間半ほど経過したところで、そんなことをする必要はないと気づく。できるだけスコアが上がるような貪欲を${O}(N^2)$でやればいいだけだった。
$10^9$から下って約数を400以上持つ整数を6000個列挙して、約数がもっとも増えるものを貪欲に取っていくと41200くらい。そこから山登りして41500くらい。
リアルタイムでchokudaiさんのヒントがあったらしい。でも、気づいていたら逆にこれに囚われてしまって苦戦しそう。
