Submission #1370787

---

Source Code Expand

#include<string>
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<map>
#include<functional>
#include<chrono>
#include<random>
using namespace std;
using namespace chrono;
typedef long long int llint;
typedef bool izryt;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
const int big=1e9;//daikon3の評価関数
const int xline=7;
const int oline=17;
const int n=50;
const int renp=50;//一つつなげると得点
const int norenp=300;
const int bra=50;//両方バランスよく残すと高得点
const int brn[10]={0,20,15,12,10,8,6,5,4,3};//×どうしがつながってないと得点
//バランスよく広げる目的
const int yokozuna=10;//横のつながり
const int hava=30;
const int maxtime=9000;
//const int loopnum=2000;
const int pasno=75;//今が.の時のパス確率
const int pasup=50;//今が+の時の確立
decltype(chrono::system_clock::now()) starttime;
std::random_device seed_gen;
mt19937 engine(seed_gen());
int gettime(){auto nowtime=system_clock::now();
	milliseconds ret=duration_cast<milliseconds>(nowtime-starttime);
	return ret.count();
}
string drop(string in){
	string out;
	for(int i=0;i<n;i++){if(in[i]!='.'){out.pub(in[i]);}}
	return out;
}
pair<int,int> hantei(const string& befcol,string& kou){
	int ans=0;
	int i,j,ok=0,xk=0,oy=0,xy=0;
	for(i=0;i<kou.size();i++){
		if(kou[i]!='x'){continue;}
		if(befcol[i]!='x'&&(i==0||kou[i-1]!='x')){kou[i]='v';continue;}//つながってないのでダメ
		xk++;
		for(j=i;j>0;j--){
			if(kou[j-1]=='v'){kou[j-1]='x';xk++;}//復活チャンス
			else{break;}
		}
		for(j=i-1;j>0&&kou[j-1]!='x'&&i-j<10;j--){
			ans+=brn[i-j];
		}
	}
	for(i=0;i<kou.size();i++){
		if(kou[i]!='o'){continue;}
		if(befcol[i]!='o'&&(i==0||kou[i-1]!='o')){kou[i]='p';continue;}//つながってないのでダメ
		ok++;
		for(j=i;j>0;j--){
			if(kou[j-1]=='p'){kou[j-1]='o';ok++;}//復活チャンス
			else{break;}
		}
		for(j=i-1;j>0&&kou[j-1]!='o'&&i-j<10;j--){
			ans+=brn[i-j];
		}
	}
	for(i=0;i<kou.size();i++){
		if(befcol[i]=='p'&&kou[i]=='o'){ok++;}
		if(befcol[i]=='v'&&kou[i]=='x'){xk++;}
		if(befcol[i]=='p'&&kou[i]=='p'){oy++;}
		if(befcol[i]=='v'&&kou[i]=='v'){xy++;}
	}
	ans+=(ok+xk)*(norenp+renp);
	ans+=(oy+xy)*yokozuna;
	ans+=(ok*xk)*bra;
	return mp(ans,ok+xk);
}
int main(void){
	starttime=system_clock::now();
	std::uint32_t seed = std::random_device()();
	engine.seed(seed);
	bool debug=false;
	int h,i,j,k,gen;
	vector<string>mat(n);//mat[横の行][高さ]でアクセスする。
	for(i=0;i<n;i++){mat[i].res(n);}
	string str;
	for(i=n-1;i>=0;i--){
		cin>>str;
		for(j=0;j<n;j++){
			mat[j][i]=str[j];
		}
		if(str.size()>n){debug=true;}
	}
	//cout<<"q";
	priority_queue<tuple<int,int,string,vector<string>>,
		vector<tuple<int,int,string,vector<string>>>,
		greater<tuple<int,int,string,vector<string>>>
	>nowcol;//今の落下後のものを記録
	//少ない順に出てくるので多いものが残る
	//これのtop()と比較してより得点が高いならpush＆pop
	//現在評価,連結数,最後の落ちた後,答えの探索
	vector<tuple<int,int,string,vector<string>>> befcol(hava);//前の落下後の行を記録
	vector<string> vs;
	
	str.res(n);
	for(i=0;i<n;i++){str[i]='+';}
	for(h=0;h<hava;h++){
		int xl=xline;
		int ol=oline;
		str[xl]='x';
		str[ol]='o';
		befcol[h]=mt(0,0,str,vs);
		str[xl]='+';
		str[ol]='+';
	}
	//cout<<"we";
	for(i=0;i<n;i++){
		//cout<<"qdxf";
		//int dot=0;
		//for(j=0;j<n;j++){if(mat[i][j]=='.'){dot++;}}
		string deans;
		while(gettime()<(i+1)*maxtime/50.0){
			unsigned int bit=engine();
			int nowdo=0;
			string kou=mat[i];
			for(j=0;j<n;j++){
				if(kou[j]!='.'){continue;}
				if(bit&(1<<nowdo)){kou[j]='+';
					if(engine()%100>pasup){nowdo++;}
				}else{if(engine()%100>pasno){nowdo++;}}
				if(nowdo>30){nowdo=0;bit=engine();}
			}
			string kore=kou;
			kou=drop(move(kou));
			string motokou=kou;
			
			for(j=0;j<hava;j++){
				kou=motokou;
				pair<int,int>p;
				p=hantei(get<2>(befcol[j]),kou);
				if(hava<=nowcol.size()&&get<0>(nowcol.top())>=get<1>(befcol[j])*renp+p.fir){continue;}
				if(hava==nowcol.size()){nowcol.pop();}
				vs.clear();
				vs=get<3>(befcol[j]);
				vs.push_back(kore);
				nowcol.push(mt(get<1>(befcol[j])*renp+p.fir,get<1>(befcol[j])+p.sec,kou,vs));
				if(debug){deans=kou;}
				break;
			}
		}
		befcol.clear();
		befcol.res(nowcol.size());
		j=0;
		while(!nowcol.empty()){
			befcol[j]=move(nowcol.top());
			while(get<2>(befcol[j]).size()<n){get<2>(befcol[j]).pub('*');}
			nowcol.pop();j++;
		}
		if(debug){cout<<deans<<endl;
			//cout<<"de"<<get<0>(befcol[hava-1])<<" "<<get<1>(befcol[hava-1])<<" "<<get<2>(befcol[hava-1])<<endl;
		}
	}
	//befcolのうちget<1>が最大を見つける
	vector<string>ans;
	int maxpot=0,thpot=0;
	for(i=0;i<hava;i++){
		if(maxpot<get<1>(befcol[i])){maxpot=get<1>(befcol[i]);thpot=i;}
	}
	ans=get<3>(befcol[thpot]);
	for(i=n-1;i>=0;i--){
		for(j=0;j<n;j++){
			cout<<ans[j][i];
		}
		cout<<endl;
	}
	vector<string>go(n);
	if(debug){
		for(i=0;i<n;i++){go[i]=drop(ans[i]);}
		for(i=0;i<n;i++){while(go[i].size()<n){go[i].pub('*');}}
		cout<<endl;cout<<get<1>(befcol[thpot])<<endl;cout<<endl;
		int oxnum=0;
		
		str.clear();str.res(n);
		for(i=0;i<n;i++){str[i]='+';}
		str[xline]='x';
		str[oline]='o';
		for(i=0;i<n;i++){
			hantei(str,go[i]);
			str=go[i];
		}
		for(i=0;i<n;i++){for(j=0;j<n;j++){if(go[i][j]=='o'||go[i][j]=='x'){oxnum++;}}}
		cout<<"oxnum="<<oxnum<<endl;
	for(i=n-1;i>=0;i--){
		for(j=0;j<n;j++){
			cout<<go[j][i];
		}
		cout<<endl;
	}}
	return 0;
}

Submission Info

Judge Result