競プロ参加日記018 Chokudai Contest 005

Chokudai Contest 005 - AtCoder

プチマラソンコンテスト？
個人参加してみました。

・結果

49,990,247点で68位でした。
やりたいことはやったので満足です。

・解答1-適当　49500000

N*N全場所に対して、カラー1で塗るコードを提出。

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
int main(){
   int id,N,K;
   cin>>id>>N>>K;
   int S[N];
   for(int i=0;i<N;i++){
       cin>>S[i];
   }
   cout<<min(N*N,10000)<<endl;
   for(int i=0;i<min(N*N,10000);i++){
       cout<<i%N+1<<" "<<i/N+1<<" 1"<<endl;
   }
}

想定通り49500000点獲得 
問題文の読み間違いなどがないことを確認した。

・解答2-隣り合う色が多いところを選択　49986710

一回の色変更に着目すると、その色変更する領域と隣り合う色を数えて、一番数の多い色に変えた方がお得そうです。(領域がより大きく広がる)
色を変える位置も左上からではなく、何かルールがあったほうが良さそうなので、一番領域の大きいところとしました。

#include<bits/stdc++.h>
#include<atcoder/all>

using namespace std;
using namespace atcoder;

string S[100];
int id,N,K;
int Si[100][100];
vector<vector<int>> ans;

int dfsc(int x,int y,char c){
   //cout<<x<<","<<y<<","<<c<<endl;
   int dx[4]={0,0,1,-1};
   int dy[4]={1,-1,0,0};
   Si[y][x]=-2;
   int ct=1;
   for(int i=0;i<4;i++){
       if(x+dx[i]>=0&&x+dx[i]<100&&y+dy[i]>=0&&y+dy[i]<100){
           if(Si[y+dy[i]][x+dx[i]]==-1&&S[y+dy[i]][x+dx[i]]==c){
               ct+=dfsc(x+dx[i],y+dy[i],c);
           }
       }
   }
   return ct;
}

int dfsc2c[10];
void dfsc2(int x,int y,char c){
   int dx[4]={0,0,1,-1};
   int dy[4]={1,-1,0,0};
   Si[y][x]=-3;
   for(int i=0;i<4;i++){
       if(x+dx[i]>=0&&x+dx[i]<100&&y+dy[i]>=0&&y+dy[i]<100){
           if(S[y+dy[i]][x+dx[i]]==c){
               if(Si[y+dy[i]][x+dx[i]]==-2){
                   dfsc2(x+dx[i],y+dy[i],c);
               }
           }
           else{
               dfsc2c[S[y+dy[i]][x+dx[i]]-'0']++;
           }
       }
   }
}

void dfsn(int x,int y,char c,char c2){
   int dx[4]={0,0,1,-1};
   int dy[4]={1,-1,0,0};
   Si[y][x]=-4;
   S[y][x]=c;
   for(int i=0;i<4;i++){
       if(x+dx[i]>=0&&x+dx[i]<100&&y+dy[i]>=0&&y+dy[i]<100){
           if(S[y+dy[i]][x+dx[i]]==c2){
               if(Si[y+dy[i]][x+dx[i]]==-3){
                   dfsn(x+dx[i],y+dy[i],c,c2);
               }
           }
       }
   }
}

int main(){
   cin>>id>>N>>K;


   for(int i=0;i<N;i++){
       cin>>S[i];
   }

   while(1){
       for(int i=0;i<N;i++){
           for(int j=0;j<N;j++){
               Si[i][j]=-1;
           }
       }

       int mxi=-1,mxj=-1,mxc=-1;
       char mxcc='1';
       for(int i=0;i<N;i++){
           for(int j=0;j<N;j++){
               if(Si[i][j]==-1){
                   int ct;
                   ct=dfsc(j,i,S[i][j]);
                   //cout<<i<<","<<j<<","<<ct<<endl;
                   if(mxc<ct){
                       mxi=i;
                       mxj=j;
                       mxc=ct;
                       mxcc=S[i][j];
                   }
               }
           }
       }

       if(mxc==N*N) break;

       for(int i=0;i<10;i++){
           dfsc2c[i]=0;
       }
       dfsc2(mxj,mxi,mxcc);
       int mxi2=-1,mxc2=-1;
       for(int i=0;i<10;i++){
           if(mxc2<dfsc2c[i]){
               mxi2=i;
               mxc2=dfsc2c[i];
           }
       }

       vector<int> tmpv;
       tmpv.push_back(mxi);
       tmpv.push_back(mxj);
       tmpv.push_back(mxi2);

       ans.push_back(tmpv);

       dfsn(mxj,mxi,mxi2+'0',mxcc);

       //cout<<mxi<<" "<<mxj<<" "<<mxi2<<" "<<mxcc<<" "<<mxc<<endl;
       /*for(int i=0;i<N;i++){
           cout<<S[i]<<endl;
       }*/
   }

   cout<<ans.size()<<endl;
   for(int i=0;i<ans.size();i++){
       cout<<ans[i][0]+1<<" "<<ans[i][1]+1<<" "<<ans[i][2]<<endl;
   }
}

※https://atcoder.jp/contests/chokudai005/submissions/17067394
　めっちゃバグらせてました。
　
　関数の役割は以下の通りです。
　dfsc　領域の大きさを計算
　dfsc2　領域の周りにある色の数を計算
　dfsn　塗りつぶし処理

・解答3-ランダムに頼る　49990106

色を変える位置も左上からではなく、何かルールがあったほうが良さそうなので、一番領域の大きいところとしました。

解答2では、毎回の色変更ごとに一番領域の大きいところを求めていましたが、領域は広がっていくため、毎回求める必要はありません。(初めに一番領域の広いところの領域が次以降も大きくなる)

この考えになった時に、この問題は同じところを連打して、どんどん領域を広げていくのが正しいのではないかな？と思いました。

そうなったときに連打する位置を決めないといけません。
高得点が取れている一番領域の広いところは採用として、時間いっぱいまでランダムを回すようにしました。

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
string S[100],S2[100];
int id,N,K;
int Si[100][100];
vector<vector<int>> ans;
int dfsc(int x,int y,char c){
   //cout<<x<<","<<y<<","<<c<<endl;
   int dx[4]={0,0,1,-1};
   int dy[4]={1,-1,0,0};
   Si[y][x]=-2;
   int ct=1;
   for(int i=0;i<4;i++){
       if(x+dx[i]>=0&&x+dx[i]<100&&y+dy[i]>=0&&y+dy[i]<100){
           if(Si[y+dy[i]][x+dx[i]]==-1&&S[y+dy[i]][x+dx[i]]==c){
               ct+=dfsc(x+dx[i],y+dy[i],c);
           }
       }
   }
   return ct;
}
int dfsc2c[10];
void dfsc2(int x,int y,char c){
   int dx[4]={0,0,1,-1};
   int dy[4]={1,-1,0,0};
   Si[y][x]=-3;
   for(int i=0;i<4;i++){
       if(x+dx[i]>=0&&x+dx[i]<100&&y+dy[i]>=0&&y+dy[i]<100){
           if(S[y+dy[i]][x+dx[i]]==c){
               if(Si[y+dy[i]][x+dx[i]]==-2){
                   dfsc2(x+dx[i],y+dy[i],c);
               }
           }
           else{
               dfsc2c[S[y+dy[i]][x+dx[i]]-'0']++;
           }
       }
   }
}
void dfsn(int x,int y,char c,char c2){
   int dx[4]={0,0,1,-1};
   int dy[4]={1,-1,0,0};
   Si[y][x]=-4;
   S[y][x]=c;
   for(int i=0;i<4;i++){
       if(x+dx[i]>=0&&x+dx[i]<100&&y+dy[i]>=0&&y+dy[i]<100){
           if(S[y+dy[i]][x+dx[i]]==c2){
               if(Si[y+dy[i]][x+dx[i]]==-3){
                   dfsn(x+dx[i],y+dy[i],c,c2);
               }
           }
       }
   }
}
void sol1(){
   while(1){
       for(int i=0;i<N;i++){
           for(int j=0;j<N;j++){
               Si[i][j]=-1;
           }
       }
       int mxi=-1,mxj=-1,mxc=-1;
       char mxcc='1';
       for(int i=0;i<N;i++){
           for(int j=0;j<N;j++){
               if(Si[i][j]==-1){
                   int ct;
                   ct=dfsc(j,i,S[i][j]);
                   //cout<<i<<","<<j<<","<<ct<<endl;
                   if(mxc<ct){
                       mxi=i;
                       mxj=j;
                       mxc=ct;
                       mxcc=S[i][j];
                   }
               }
           }
       }
       if(mxc==N*N) break;
       for(int i=0;i<10;i++){
           dfsc2c[i]=0;
       }
       dfsc2(mxj,mxi,mxcc);
       int mxi2=-1,mxc2=-1;
       for(int i=0;i<10;i++){
           if(mxc2<dfsc2c[i]){
               mxi2=i;
               mxc2=dfsc2c[i];
           }
       }
       vector<int> tmpv;
       tmpv.push_back(mxi);
       tmpv.push_back(mxj);
       tmpv.push_back(mxi2);
       ans.push_back(tmpv);
       dfsn(mxj,mxi,mxi2+'0',mxcc);
       //cout<<mxi<<" "<<mxj<<" "<<mxi2<<" "<<mxcc<<" "<<mxc<<endl;
       /*for(int i=0;i<N;i++){
           cout<<S[i]<<endl;
       }*/
   }
}
int main(){
   std::chrono::system_clock::time_point  start, end;
   start = std::chrono::system_clock::now();
   cin>>id>>N>>K;
   srand(12345);
   for(int i=0;i<N;i++){
       cin>>S2[i];
   }
   for(int i=0;i<N;i++){
       S[i]=S2[i];
   }
   sol1();
   while(1){
       int mxi=rand()%N;
       int mxj=rand()%N;
       vector<vector<int>> anstmp;
       for(int i=0;i<N;i++){
           S[i]=S2[i];
       }
       while(1){
           for(int i=0;i<N;i++){
               for(int j=0;j<N;j++){
                   Si[i][j]=-1;
               }
           }
           int mxc=-1;
           char mxcc='1';
           int ct=dfsc(mxj,mxi,S[mxi][mxj]);
           mxc=ct;
           mxcc=S[mxi][mxj];
           if(mxc==N*N) break;
           for(int i=0;i<10;i++){
               dfsc2c[i]=0;
           }
           dfsc2(mxj,mxi,mxcc);
           int mxi2=-1,mxc2=-1;
           for(int i=0;i<10;i++){
               if(mxc2<dfsc2c[i]){
                   mxi2=i;
                   mxc2=dfsc2c[i];
               }
           }
           vector<int> tmpv;
           tmpv.push_back(mxi);
           tmpv.push_back(mxj);
           tmpv.push_back(mxi2);
           anstmp.push_back(tmpv);
           dfsn(mxj,mxi,mxi2+'0',mxcc);
           //cout<<mxi<<" "<<mxj<<" "<<mxi2<<" "<<mxcc<<" "<<mxc<<endl;
           /*for(int i=0;i<N;i++){
               cout<<S[i]<<endl;
           }*/
       }
       //cout<<anstmp.size()<<endl;
       if(ans.empty()||ans.size()>anstmp.size()){
           ans=anstmp;
       }
       end = std::chrono::system_clock::now();
       double elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count();
      // cout<<elapsed<<endl;
       if(elapsed>2900) break;
   }
   cout<<ans.size()<<endl;
   for(int i=0;i<ans.size();i++){
       cout<<ans[i][0]+1<<" "<<ans[i][1]+1<<" "<<ans[i][2]<<endl;
   }
}

　増えた関数の役割は以下の通りです。
　sol1　解答2の解法で解きます
　　　　mainではランダムで処理時間が2900msになるまで回します。
　　　　ランダムと解答2で操作手順の少ないほうを採用としています。

・解答4-ランダムパターンを増やす　49990247

残り案も少ないため、ランダムパターン(シードの種類)を増やすことでスコアを上げようとしました。
具体的には、ローカル環境での答えを埋め込んで、別シードの答えのランダム解と比較するということをしました。

(本当はランダム回数を増やしたかったのですが、実装等に時間がかかり、3s*50ファイルが残り時間から見てぎりぎりだったため、断念しました。)

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
string S[100],S2[100];
int id,N,K;
int Si[100][100];
vector<vector<int>> ans;
int aaa,bbb,ccc;
void idorder(int id){
   aaa=1,bbb=1,ccc=999;
   if(id==1){aaa=49;bbb=48;ccc=197;}
   if(id==2){aaa=49;bbb=48;ccc=192;}
   if(id==3){aaa=49;bbb=48;ccc=196;}
   if(id==4){aaa=49;bbb=48;ccc=192;}
   if(id==5){aaa=58;bbb=61;ccc=202;}
   if(id==6){aaa=49;bbb=48;ccc=188;}
   if(id==7){aaa=49;bbb=48;ccc=196;}
   if(id==8){aaa=49;bbb=48;ccc=205;}
   if(id==9){aaa=61;bbb=52;ccc=198;}
   if(id==10){aaa=61;bbb=52;ccc=198;}
   if(id==11){aaa=61;bbb=52;ccc=198;}
   if(id==12){aaa=61;bbb=52;ccc=198;}
   if(id==13){aaa=61;bbb=52;ccc=198;}
   if(id==14){aaa=61;bbb=52;ccc=198;}
   if(id==15){aaa=61;bbb=52;ccc=198;}
   if(id==16){aaa=61;bbb=52;ccc=198;}
   if(id==17){aaa=61;bbb=52;ccc=198;}
   if(id==18){aaa=61;bbb=52;ccc=198;}
   if(id==19){aaa=61;bbb=52;ccc=198;}
   if(id==20){aaa=61;bbb=52;ccc=198;}
   if(id==21){aaa=61;bbb=52;ccc=198;}
   if(id==22){aaa=61;bbb=52;ccc=198;}
   if(id==23){aaa=61;bbb=52;ccc=198;}
   if(id==24){aaa=61;bbb=52;ccc=198;}
   if(id==25){aaa=61;bbb=52;ccc=198;}
   if(id==26){aaa=61;bbb=52;ccc=198;}
   if(id==27){aaa=61;bbb=52;ccc=198;}
   if(id==28){aaa=61;bbb=52;ccc=198;}
   if(id==29){aaa=61;bbb=52;ccc=198;}
   if(id==30){aaa=61;bbb=52;ccc=198;}
   if(id==31){aaa=61;bbb=52;ccc=198;}
   if(id==32){aaa=61;bbb=52;ccc=198;}
   if(id==33){aaa=61;bbb=52;ccc=198;}
   if(id==34){aaa=61;bbb=52;ccc=198;}
   if(id==35){aaa=61;bbb=52;ccc=198;}
   if(id==36){aaa=61;bbb=52;ccc=198;}
   if(id==37){aaa=61;bbb=52;ccc=198;}
   if(id==38){aaa=61;bbb=52;ccc=198;}
   if(id==39){aaa=61;bbb=52;ccc=198;}
   if(id==40){aaa=61;bbb=52;ccc=198;}
   if(id==41){aaa=61;bbb=52;ccc=198;}
   if(id==42){aaa=61;bbb=52;ccc=198;}
   if(id==43){aaa=61;bbb=52;ccc=198;}
   if(id==44){aaa=61;bbb=52;ccc=198;}
   if(id==45){aaa=61;bbb=52;ccc=198;}
   if(id==46){aaa=61;bbb=52;ccc=198;}
   if(id==47){aaa=61;bbb=52;ccc=198;}
   if(id==48){aaa=61;bbb=52;ccc=198;}
   if(id==49){aaa=61;bbb=52;ccc=198;}
   if(id==50){aaa=61;bbb=52;ccc=198;}
   aaa--;
   bbb--;
}
void fin(string filename){
   //cout<<filename<<endl;
   std::ifstream ifs(filename);
   std::string str;
   int i=0;
   getline(ifs, str);
   while (getline(ifs, str))
   {
       //cout<<str<<endl;
       S2[i++]=str;
   }
}
int dfsc(int x,int y,char c){
   //cout<<x<<","<<y<<","<<c<<endl;
   int dx[4]={0,0,1,-1};
   int dy[4]={1,-1,0,0};
   Si[y][x]=-2;
   int ct=1;
   for(int i=0;i<4;i++){
       if(x+dx[i]>=0&&x+dx[i]<100&&y+dy[i]>=0&&y+dy[i]<100){
           if(Si[y+dy[i]][x+dx[i]]==-1&&S[y+dy[i]][x+dx[i]]==c){
               ct+=dfsc(x+dx[i],y+dy[i],c);
           }
       }
   }
   return ct;
}
int dfsc2c[10];
void dfsc2(int x,int y,char c){
   int dx[4]={0,0,1,-1};
   int dy[4]={1,-1,0,0};
   Si[y][x]=-3;
   for(int i=0;i<4;i++){
       if(x+dx[i]>=0&&x+dx[i]<100&&y+dy[i]>=0&&y+dy[i]<100){
           if(S[y+dy[i]][x+dx[i]]==c){
               if(Si[y+dy[i]][x+dx[i]]==-2){
                   dfsc2(x+dx[i],y+dy[i],c);
               }
           }
           else{
               dfsc2c[S[y+dy[i]][x+dx[i]]-'0']++;
           }
       }
   }
}
void dfsn(int x,int y,char c,char c2){
   int dx[4]={0,0,1,-1};
   int dy[4]={1,-1,0,0};
   Si[y][x]=-4;
   S[y][x]=c;
   for(int i=0;i<4;i++){
       if(x+dx[i]>=0&&x+dx[i]<100&&y+dy[i]>=0&&y+dy[i]<100){
           if(S[y+dy[i]][x+dx[i]]==c2){
               if(Si[y+dy[i]][x+dx[i]]==-3){
                   dfsn(x+dx[i],y+dy[i],c,c2);
               }
           }
       }
   }
}
void sol2(){
   idorder(id);
   int mxi=aaa;
   int mxj=bbb;
   vector<vector<int>> anstmp;
   for(int i=0;i<N;i++){
       S[i]=S2[i];
   }
   while(1){
       for(int i=0;i<N;i++){
           for(int j=0;j<N;j++){
               Si[i][j]=-1;
           }
       }
       int mxc=-1;
       char mxcc='1';
       int ct=dfsc(mxj,mxi,S[mxi][mxj]);
       mxc=ct;
       mxcc=S[mxi][mxj];
       if(mxc==N*N) break;
       for(int i=0;i<10;i++){
           dfsc2c[i]=0;
       }
       dfsc2(mxj,mxi,mxcc);
       int mxi2=-1,mxc2=-1;
       for(int i=0;i<10;i++){
           if(mxc2<dfsc2c[i]){
               mxi2=i;
               mxc2=dfsc2c[i];
           }
       }
       vector<int> tmpv;
       tmpv.push_back(mxi);
       tmpv.push_back(mxj);
       tmpv.push_back(mxi2);
       anstmp.push_back(tmpv);
       dfsn(mxj,mxi,mxi2+'0',mxcc);
       //cout<<mxi<<" "<<mxj<<" "<<mxi2<<" "<<mxcc<<" "<<mxc<<endl;
       /*for(int i=0;i<N;i++){
           cout<<S[i]<<endl;
       }*/
   }
   //cout<<anstmp.size()<<endl;
   if(ans.empty()||ans.size()>anstmp.size()){
       ans=anstmp;
   }
}
void sol1(){
       while(1){
       for(int i=0;i<N;i++){
           for(int j=0;j<N;j++){
               Si[i][j]=-1;
           }
       }
       int mxi=-1,mxj=-1,mxc=-1;
       char mxcc='1';
       for(int i=0;i<N;i++){
           for(int j=0;j<N;j++){
               if(Si[i][j]==-1){
                   int ct;
                   ct=dfsc(j,i,S[i][j]);
                   //cout<<i<<","<<j<<","<<ct<<endl;
                   if(mxc<ct){
                       mxi=i;
                       mxj=j;
                       mxc=ct;
                       mxcc=S[i][j];
                   }
               }
           }
       }
       if(mxc==N*N) break;
       for(int i=0;i<10;i++){
           dfsc2c[i]=0;
       }
       dfsc2(mxj,mxi,mxcc);
       int mxi2=-1,mxc2=-1;
       for(int i=0;i<10;i++){
           if(mxc2<dfsc2c[i]){
               mxi2=i;
               mxc2=dfsc2c[i];
           }
       }
       vector<int> tmpv;
       tmpv.push_back(mxi);
       tmpv.push_back(mxj);
       tmpv.push_back(mxi2);
       ans.push_back(tmpv);
       dfsn(mxj,mxi,mxi2+'0',mxcc);
       //cout<<mxi<<" "<<mxj<<" "<<mxi2<<" "<<mxcc<<" "<<mxc<<endl;
       /*for(int i=0;i<N;i++){
           cout<<S[i]<<endl;
       }*/
   }
}
void numsmake(){
   cout<<"string nums[50]={";
   for(int i=0;i<50;i++){
       cout<<"\""<<i+1<<"\",";
   }
   cout<<"\"0\""<<"}"<<endl;
}
void randmake(){
   std::chrono::system_clock::time_point  start, end;
   start = std::chrono::system_clock::now();
   string nums[50]={"1","2","3","4","5","6","7","8","9","10","11","12","13","14","15","16","17","18","19","20","21","22","23","24","25","26","27","28","29","30","31","32","33","34","35","36","37","38","39","40","41","42","43","44","45","46","47","48","49","50"};
   for(int ff=1;ff<=50;ff++){
       fin("C:\\Users\\nullkara\\Downloads\\dataset\\in\\subtask_01_0"+nums[ff-1]+".txt");
       //cin>>id>>N>>K;
       id=ff;
       N=100;
       K=9;
       srand(12345);
       /*for(int i=0;i<N;i++){
           cout<<S2[i]<<endl;;
       }*/
       for(int i=0;i<N;i++){
           S[i]=S2[i];
       }
       start = std::chrono::system_clock::now();
       sol1();
       sol2();
       while(1){
           int mxi=rand()%N;
           int mxj=rand()%N;
           vector<vector<int>> anstmp;
           for(int i=0;i<N;i++){
               S[i]=S2[i];
           }
           while(1){
               for(int i=0;i<N;i++){
                   for(int j=0;j<N;j++){
                       Si[i][j]=-1;
                   }
               }
               int mxc=-1;
               char mxcc='1';
               int ct=dfsc(mxj,mxi,S[mxi][mxj]);
               mxc=ct;
               mxcc=S[mxi][mxj];
               if(mxc==N*N) break;
               for(int i=0;i<10;i++){
                   dfsc2c[i]=0;
               }
               dfsc2(mxj,mxi,mxcc);
               int mxi2=-1,mxc2=-1;
               for(int i=0;i<10;i++){
                   if(mxc2<dfsc2c[i]){
                       mxi2=i;
                       mxc2=dfsc2c[i];
                   }
               }
               vector<int> tmpv;
               tmpv.push_back(mxi);
               tmpv.push_back(mxj);
               tmpv.push_back(mxi2);
               anstmp.push_back(tmpv);
               dfsn(mxj,mxi,mxi2+'0',mxcc);
               //cout<<mxi<<" "<<mxj<<" "<<mxi2<<" "<<mxcc<<" "<<mxc<<endl;
               /*for(int i=0;i<N;i++){
                   cout<<S[i]<<endl;
               }*/
           }
           //cout<<anstmp.size()<<endl;
           if(ans.empty()||ans.size()>anstmp.size()){
               ans=anstmp;
           }
           end = std::chrono::system_clock::now();
           double elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count();
          // cout<<elapsed<<endl;
           if(elapsed>2900) break;
       }
       /*cout<<ans.size()<<endl;
       for(int i=0;i<ans.size();i++){
           cout<<ans[i][0]+1<<" "<<ans[i][1]+1<<" "<<ans[i][2]<<endl;
       }*/
       cout<<"if(id=="<<id<<"){";
       cout<<"aaa="<<ans[0][0]+1<<";";
       cout<<"bbb="<<ans[0][1]+1<<";";
       cout<<"ccc="<<ans.size()<<";";
       cout<<"}"<<endl;
   }
}
int main(){
   std::chrono::system_clock::time_point  start, end;
   start = std::chrono::system_clock::now();
   cin>>id>>N>>K;
   srand(34557);
   for(int i=0;i<N;i++){
       cin>>S2[i];
   }
   for(int i=0;i<N;i++){
       S[i]=S2[i];
   }
   sol1();
   sol2();
   int ttt=0;
   while(1){
       int mxi;
       int mxj;
       if(ttt==0){
           mxi=48;
           mxj=47;
       }
       else if(ttt==1){
           mxi=57;
           mxj=60;
       }
       else if(ttt==2){
           mxi=48;
           mxj=47;
       }
       else if(ttt==3){
           mxi=60;
           mxj=51;
       }
       else{
           mxi=rand()%N;
           mxj=rand()%N;
       }
       ttt++;
       vector<vector<int>> anstmp;
       for(int i=0;i<N;i++){
           S[i]=S2[i];
       }
       while(1){
           for(int i=0;i<N;i++){
               for(int j=0;j<N;j++){
                   Si[i][j]=-1;
               }
           }
           int mxc=-1;
           char mxcc='1';
           int ct=dfsc(mxj,mxi,S[mxi][mxj]);
           mxc=ct;
           mxcc=S[mxi][mxj];
           if(mxc==N*N) break;
           for(int i=0;i<10;i++){
               dfsc2c[i]=0;
           }
           dfsc2(mxj,mxi,mxcc);
           int mxi2=-1,mxc2=-1;
           for(int i=0;i<10;i++){
               if(mxc2<dfsc2c[i]){
                   mxi2=i;
                   mxc2=dfsc2c[i];
               }
           }
           vector<int> tmpv;
           tmpv.push_back(mxi);
           tmpv.push_back(mxj);
           tmpv.push_back(mxi2);
           anstmp.push_back(tmpv);
           dfsn(mxj,mxi,mxi2+'0',mxcc);
           //cout<<mxi<<" "<<mxj<<" "<<mxi2<<" "<<mxcc<<" "<<mxc<<endl;
           /*for(int i=0;i<N;i++){
               cout<<S[i]<<endl;
           }*/
       }
       //cout<<anstmp.size()<<endl;
       if(ans.empty()||ans.size()>anstmp.size()){
           ans=anstmp;
       }
       end = std::chrono::system_clock::now();
       double elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end-start).count();
      // cout<<elapsed<<endl;
       if(elapsed>2900) break;
   }
   cout<<ans.size()<<endl;
   for(int i=0;i<ans.size();i++){
       cout<<ans[i][0]+1<<" "<<ans[i][1]+1<<" "<<ans[i][2]<<endl;
   }
}

増えた関数の役割は以下の通りです。
idorder　別シードでの結果を返しますです。aaaがy座標、bbbがx座標、cccが操作回数です。srand(12345)の結果が埋め込んでいると思います。
fin　入力をファイルから読み込み関数です。N,Kは固定で、idはファイル名と連動しているため読み捨てています。
sol2　idorderの埋め込み結果で連打位置を決めて解答する関数です。
numsmake　randmake関数にある、num配列を手で作る時間がなかったのでプログラムに作らせました。
randmake　idorderの中身を作る、埋め込みようの関数です。後半のcoutを見てわかる通り、出力結果をそのままidorderに貼り付ければ動くようにしています。

mainでは、以下のような事をしています。
sol1,sol2,ランダム(シード34557)の解法の中で一番操作回数が少ないものを採用。
idorderの中身を見てみると、4パターンくらいしかなかったので、そのパターンはどのidでも行うようにした。(これがあるのでsol2が無駄になっていますね...)

 ・考察とか

合っているかは分かりませんが、idorderの埋め込み結果を見た感じaaaとbbbが中央付近に固まっているため、連打する位置は真ん中あたりが良さそうです。
ランダム範囲も、真ん中あたりに絞ると結果がよくなりそうです。

あと50人チームで組んでいる場合、それぞれのidごとに最適な解法を各々が組むのが多分最強。

・追記解答-真ん中探索　49990689

mainのランダムの範囲を

           mxi=rand()%20+40;
           mxj=rand()%20+40;

としました。あと、setを使って同じ連打位置をランダムによって選択した場合は、探索しないようにしました。
https://atcoder.jp/contests/chokudai005/submissions/17074089
スコアが微増しました。順位だと51位でしょうか。考察の真ん中が良さそうは正しそうですね。

・追記解答2-ランダム回数の増加　49990757

埋め込むランダム解の回数を増やしました。
60秒間ランダムを回して、30秒は全範囲から、あと30秒は追記解答のように真ん中範囲から探すようにしました。あとシードは1192794としました。

https://atcoder.jp/contests/chokudai005/submissions/17074811
49990757点で本番中に出せてた場合、順位は50位。伸びが悪いので、現状のアルゴリズムの限界はここ辺りかな？ccc見た感じ、ほとんどが操作回数182回なので、同じ個所連打の最高スコアはこの辺り？

※現状１位のスコアのコードを実行したところ、同じ個所連打で130くらいになっている。
　その連打位置で、僕のソースで実行させても180回なので、何色に変えるかってところに改善の余地があるっぽい。

・終わりに

参加人数が553人と寂しいなぁと思いました。rateのコンテストより楽しいのに。
こういうコンテスト、定期的に欲しいですね。お願いします！！