競プロ参加日記018 Chokudai Contest 005
プチマラソンコンテスト?
個人参加してみました。
・結果
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回なので、同じ個所連打の最高スコアはこの辺り?
※現状1位のスコアのコードを実行したところ、同じ個所連打で130くらいになっている。
その連打位置で、僕のソースで実行させても180回なので、何色に変えるかってところに改善の余地があるっぽい。
・終わりに
参加人数が553人と寂しいなぁと思いました。rateのコンテストより楽しいのに。
こういうコンテスト、定期的に欲しいですね。お願いします!!
この記事が気に入ったらサポートをしてみませんか?