競プロ参加日記004 Introduction to Heuristics Contest 参加

ぬるから

所謂、マラソンと呼ばれる形式のミニコンテストが開催されていました。
普通のマラソンコンテストと違い以下の特徴があります。
・期間が2Hと短い
・解き方が書いてある小問(B,C問題)がある
そのため、初心者に優しい感じのコンテストでした。(楽しかったので定期的にもっと開催してほしいです。)

・結果
81890786点で503位でした。(この後、改良して98908056まで伸ばしました。)

・提出コード1 0点
https://atcoder.jp/contests/intro-heuristics/submissions/14809859

void ans_ran(){
   for(int i=1;i<=D;i++){
       ans[i]=rand()%26+1;
   }
}

(マイナス点になって、無提出の人より順位が低くなるとか思っていました。)

・提出コード2 78877563点 
https://atcoder.jp/contests/intro-heuristics/submissions/14811939

void random_solve(){
   srand(1234);
   ans_ran();
   for(int i=0;i<=100000;i++){
       int bef=man_calc(false);
       int ci=rand()%D+1;
       int tn=rand()%26+1;
       int fn=ans[ci];
       change_ans(ci,tn);
       int aft=man_calc(false);
       if(bef>aft){
           change_ans(ci,fn);
       }
   }
   ans_disp();
   //cout<<man_calc(false)<<endl;
}

ランダム初期解に対して、C問題にある乱択による値の変更を適用しました。
これだけでもスコアがぐんと伸びますね！！

・提出コード3 80456452点
https://atcoder.jp/contests/intro-heuristics/submissions/14813459

void random_solve(){
   int seed=1234;
   int cnt=100000;
   srand(seed);
   ans_ran();
   for(int i=0;i<=cnt;i++){
       int bef=man_calc(false);
       int ci=rand()%D+1;
       int tn=rand()%26+1;
       int fn=ans[ci];
       change_ans(ci,tn);
       int aft=man_calc(false);
       if(bef>aft){
           change_ans(ci,fn);
       }
       if(i%(cnt/5)==0){
           //cout<<i<<endl;
           for(int ci=1;ci<=D;ci++){
               for(int tn=1;tn<=26;tn++){
                   int bef=man_calc(false);
                   int fn=ans[ci];
                   change_ans(ci,tn);
                   int aft=man_calc(false);
                   if(bef>aft){
                       change_ans(ci,fn);
                   }
               }
           }
       }
   }
   ans_disp();
   //cout<<man_calc(false)<<endl;
}

遺伝的アルゴリズムで遊んだことが昔あるのですが、この手の乱択では、最適解ではない山の方に答えが行ってしまうことがあります。
遺伝的アルゴリズムでは、それを抑えるために突然変異という変化が必要になります。(変化をたまに大きくすることによって、より最適解に近いほうの山へ移動する)
365*26通りの全パターンの値の変化を、一定周期で行うことにより突然変異的な変化を持たせようとしています。(今思うと、半分は全く違う値にするなど、もっと変化を付けたほうが突然変異っぽいですね)

・提出コード4 82085887点
https://atcoder.jp/contests/intro-heuristics/submissions/14824398

int change_ans(int i,int n,bool f){
   int ret=0;
   if(f){
       int fr=ans[i];
       ret+=s[i][n];
       ret-=s[i][fr];

       //cout<<ret<<endl;
       int fl=0;
       for(int j=1;j<=i-1;j++){
           if(ans[j]==fr) fl=0;
           else fl++;
       }
       for(int j=i;j<=D;j++){
           if(ans[j]==fr&&j!=i) break;
           ret-=c[fr]*(fl+1);
       }
       //cout<<ret<<endl;
       int tl=0;
       for(int j=1;j<=i-1;j++){
           if(ans[j]==n) tl=0;
           else tl++;
       }
       for(int j=i;j<=D;j++){
           if(ans[j]==n) break;
           ret+=c[n]*(tl+1);
       }
       //cout<<ret<<endl;
   }
   ans[i]=n;
   //cout<<ret<<endl;
   return ret;
}

void random_solve(){
   int seed=1234;
   int cnt=5000000;
   srand(seed);
   ans_ran();
   int henc=D*2;
   int hent=52;
   int bc=D/2,bt=13;
   for(int i=0;i<=cnt;i++){
       if(i%(cnt/(henc-3))==0){
           henc--;
           //cout<<henc<<endl;
       }
       if(i%(cnt/(hent-3))==0){
           hent--;
           //cout<<","<<hent<<endl;
       }
       int ci=bc+rand()%henc-henc/2;
       while(ci<=0) ci+=D;
       ci%=D;
       bc=ci;
       int tn=bt+rand()%hent-hent/2;
       while(tn<=0) tn+=26;
       tn%=26;
       bt=tn;
       int fn=ans[ci];
       if(tn==fn){
           tn=(tn+1)%26;
       }
       //cout<<ci<<","<<bt<<endl;
       int cng=change_ans(ci,tn,true);
       if(cng<0){
           change_ans(ci,fn,false);
       }
       if(i%(cnt/50)==0){
           //cout<<i<<endl;
           for(int ci=1;ci<=D;ci++){
               for(int tn=1;tn<=26;tn++){
                   int fn=ans[ci];
                   int cng=change_ans(ci,tn,true);
                   if(cng<0){
                       change_ans(ci,fn,false);
                   }
               }
           }
       }
   }
   ans_disp();
   //cout<<man_calc(false)<<endl;
}

値を変えた際に、365*26の計算を行い、満足度を再計算していたのですが、上書きする値と上書きされる値の2つの値しか満足度に影響は与えない(他の24つの値が与える満足度への影響は同じ)ため、再計算せず2つの値による変化量を求めるだけにしました。
これにより計算量が365*2に収まり、乱択の回数を増やしました。
あと、完全にランダムで値を決定するのではなく、前回の値からの変化量をランダムで決め前回値に近い値を次の乱択値として採用するようにしました。(多分、山登り法と言うらしいです)

・提出コード5 98331761
https://atcoder.jp/contests/intro-heuristics/submissions/14824958

void ans_don(){
   for(int i=1;i<=D;i++){
       int mx=-LLONG_MAX;
       int mxi=-1;
       for(int j=1;j<=26;j++){
           if(mx<s[i][j]){
               mx=s[i][j];
               mxi=j;
           }
       }
       ans[i]=mxi;
   }
}

初期値をランダムではなく、s[][]の多いものにしました。
この貪欲はB問題の誘導に書かれていたのですが、コンテスト中は何故か読み飛ばしていて、コンテスト後に気付きました。(一番の失敗)

・最後に
普段の競プロでも、趣味/業務の開発作業でも、この手の乱択アルゴリズムは使わないため楽しかったです。
長時間のマラソンコンテストに一度参加してみたいですね...。

この記事が気に入ったらサポートをしてみませんか？