読者です 読者をやめる 読者になる 読者になる

Youseiの技術メモ

競プロで書いたコードや制作物の紹介など,技術的な事を書いていきます

Chokudai Contest002 解法

問題概要

109以下の整数を100個出力しろ。出力した数の約数の集合(重複は除く)の数が多いほど良い。

コメント

本番では高度合成数を適当にいくつか出力するくらいしか分からなかった。

のでTLに流れてた回答を見て解いた。解法1を本番中に思いつきたかった...

コンテストページ

Chokudai Contest 002 - Chokudai Contest 002 | AtCoder

解法

解法1:高度合成数×素数

約数が多い高度合成数に異なる素数をかけて結果が109を超えないものを出力。

すると250-1000個程度の約数をもつ高度合成数が選ばれるので35000-40000くらいの点数が出る

提出コード:Submission #965609 - Chokudai Contest 002 | AtCoder

解法2:約数が多い数を10000個ほど挙げて焼きなまし

色々調べながらやってみた
コード:https://gist.github.com/SoichiSumi/34fb428b9b07a2f6d8df209f35087d36