Chokudai Contest 002 約数をたくさんつくろう！を解いた

マラソン問題なので、したアプローチなどを記してみる。

問題概要

以上 以下の整数を100個、それらの約数の和集合の大きさが最大になるように出力せよ。

考察

約数の個数が多いといえば、高度合成数が思い浮かぶ。 ちょうどいい高度合成数に、大きめの素数をかけてたくさん並べればスコアが出そうなので、OEISで高度合成数を探して、ランダムに素数をかけて出力してみると、高度合成数の選び方にもよるが最高33000点くらい。

よく考えると、同じ高度合成数を用意するならどんな素数をかけても効率は変わらないので、なるべく小さい素数を取りに行くことにする。 これで38000点が取れる。

逆に、素数が先にあってそこに最大の高度合成数をかけに行く形にしても、点数はほぼ変わらず。

約数をstd::mapに詰めて山登り法を100秒回すと、39000点を超えた。

メモ代わりにプログラムを貼っておく。

std::vector<int> primes;
lint ans[100],f[]={2,3,5,7,11,13};
std::map<int,int> facts;
void func(int n,bool b){
    for(int i=1;i*i<=n;i++){
        if(n%i==0){
            if(b){
                facts[i]++;
                if(i*i!=n)facts[n/i]++;
            }
            else{
                facts[i]--;
                if(facts[i]==0)facts.erase(i);
                if(i*i!=n){
                    facts[n/i]--;
                    if(facts[n/i]==0)facts.erase(n/i);
                }
            }
        }
    }
}
int main() {
    for(int i=2;i<=1000;i++){
        if(isprime(i))primes.push_back(i);
    }
    std::fill(ans,ans+100,1441440);
    int now=0;
    rep(i,100){
        while(ans[i]*primes[now]<=1e9){
            ans[i]*=primes[now];
            now++;
        }
        while(ans[i]*5<=1e9)ans[i]*=5;
        while(ans[i]*3<=1e9)ans[i]*=3;
        while(ans[i]*2<=1e9)ans[i]*=2;
        func(ans[i],true);
    }
    time_t time=clock();
    std::random_device rd;
    std::mt19937 mt(rd());
    int score=facts.size();
    while(clock()-time<=100000000){
        int change=mt()%100;
        int a=f[mt()%6],b=f[mt()%6];
        if(ans[change]%a==0&&ans[change]/a*b<=1e9){
            func(ans[change],false);
            ans[change]=ans[change]/a*b;
            func(ans[change],true);
            if(score>facts.size()){
                func(ans[change],false);
                ans[change]=ans[change]/b*a;
                func(ans[change],true);
            }
            else score=facts.size();
        }
    }
    rep(i,100)std::cout<<ans[i]<<std::endl;
    std::cout<<score<<std::endl;
    return 0;
}

感想

中2の双子が42000点以上取っていて怖い。まだまだ自分はマラソンに弱い。