Topcoder Marathon Match 96 最終結果

作成日：2018.01.10

カテゴリー：競プロ 参戦記録

目次

1. 最終結果
2. 解法
3. ソースコード
4. 反省

最終結果

　$967547.39$点で順位はシステムテスト前と変わらず$8$位。

解法

　2つの敷き詰め方を試して良かった方を採用する。 敷き詰め方はいずれもまずは周囲を埋め、中央に残った空きマスに対して伸ばせるところを伸ばす山登り(solve1)を行う。 山登りを行う際に、伸ばせる時にも$3/4$の確率で伸ばさないようにする。 このことによってランダム性が生じるので、山登りパートを時間いっぱい(それぞれ$4.99$sec)何度も繰り返し行い最も良かったものを答えとする。
　敷き詰め方のうちの一方(solveA)では、右辺と上辺を直線のワイヤでまっすぐに、左辺と下辺を曲がったワイヤでジグザグに埋めれる限り埋める。
　もう一方(solveB)では、まず曲がったワイヤでジグザグに四辺を埋めれる限り埋めていく。 そして、まだ埋めていないマスを端から直線のワイヤを用いて伸ばすことで埋めていく。

ソースコード

#include <bits/stdc++.h>
#include <sys/time.h>

using namespace std;

typedef long long LL;
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

const double MAX_TIME = 4.99;

double get_time() {
	timeval tv;
	gettimeofday(&tv, NULL);
	return tv.tv_sec + 1e-6 * tv.tv_usec;
}

unsigned int xor128(){
	static unsigned int x=987654301,y=362436069,z=521288629,w=88675123;
	unsigned int t = (x^(x<<11));
	x=y;y=z;z=w;
	return w=(w^(w>>19))^(t^(t>>8));
}

bool rnd_accept(){
	return !(xor128()&3);
}

const int MC = 102;
const int NT = 24;

class GarlandOfLights {
	const int dx[4] = {0,1,0,-1};
	const int dy[4] = {1,0,-1,0};
	const int lg[16] = {-1,0,1,-1,2,-1,-1,-1,3,-1,-1,-1,-1,-1,-1,-1};
	const int code[8] = {3,6,12,9,5,10,0,0};
	const int decode[16] = {-1,-1,-1,0,-1,4,1,-1,-1,3,5,-1,2,-1,-1,-1};
	vector<int> tile[NT];
	int tile_count[NT];
	int ini_tile_count[NT];
	int best_tile_count[NT];
	int wire_count[8];
	char ans[MC][MC];
	char best[MC][MC];
	int bestscore,nowscore;
	char ini[MC][MC];
	int H,W;
	int h_min , h_max , w_min , w_max;
	int color_num;
	
	bool horizontal(int now_x , int now_y){	//横線から縦方向に伸ばす
		int w0 = code[ans[now_x][now_y]>>2]^1;
		int w3 = code[ans[now_x][now_y+1]>>2]^4;
		int c0 = ans[now_x+dx[lg[w0]]][now_y+dy[lg[w0]]]&3;
		int c3 = ans[now_x+dx[lg[w3]]][now_y+1+dy[lg[w3]]]&3;
		++tile_count[ans[now_x][now_y]];
		++tile_count[ans[now_x][now_y+1]];
		if((!~ans[now_x+1][now_y]) && (!~ans[now_x+1][now_y+1])){
			int k1 = xor128()%color_num , k2 = xor128()%(color_num-1);
			if(k2 >= k1) ++k2;
			if(tile_count[12|k1] && tile_count[8|k2]){
				int k0 = -1 , k3 = -1;
				int r0 = decode[2|w0]<<2 , r3 = decode[2|w3]<<2;
				repp(t,0,color_num) if(t != c0 && t != k1){
					if((k0<0 && tile_count[r0|t]) || (k0>=0 && tile_count[r0|k0] < tile_count[r0|t])) k0 = t;
				}
				repp(t,0,color_num) if(t != c3 && t != k2){
					if((k3<0 && tile_count[r3|t]+((r3|t)==(r0|k0)?-1:0)) || (k3>=0 && tile_count[r3|k3] < tile_count[r3|t]+((r3|t)==(r0|k0)?-1:0))) k3 = t;
				}
				if((~k0) && (~k3) && rnd_accept()){
					--tile_count[r0|k0];
					--tile_count[12|k1];
					--tile_count[8|k2];
					--tile_count[r3|k3];
					ans[now_x][now_y] = (r0|k0);
					ans[now_x+1][now_y] = (12|k1);
					ans[now_x+1][now_y+1] = (8|k2);
					ans[now_x][now_y+1] = (r3|k3);
					--nowscore;
					return 1;
				}
			}
		}
		if((!~ans[now_x-1][now_y]) && (!~ans[now_x-1][now_y+1])){
			int k1 = xor128()%color_num , k2 = xor128()%(color_num-1);
			if(k2 >= k1) ++k2;
			if(tile_count[k1] && tile_count[4|k2]){
				int k0 = -1 , k3 = -1;
				int r0 = decode[8|w0]<<2 , r3 = decode[8|w3]<<2;
				repp(t,0,color_num) if(t != c0 && t != k1){
					if((k0<0 && tile_count[r0|t]) || (k0>=0 && tile_count[r0|k0] < tile_count[r0|t])) k0 = t;
				}
				repp(t,0,color_num) if(t != c3 && t != k2){
					if((k3<0 && tile_count[r3|t]+((r3|t)==(r0|k0)?-1:0)) || (k3>=0 && tile_count[r3|k3] < tile_count[r3|t]+((r3|t)==(r0|k0)?-1:0))) k3 = t;
				}
				if((~k0) && (~k3) && rnd_accept()){
					--tile_count[r0|k0];
					--tile_count[k1];
					--tile_count[4|k2];
					--tile_count[r3|k3];
					ans[now_x][now_y] = (r0|k0);
					ans[now_x-1][now_y] = k1;
					ans[now_x-1][now_y+1] = (4|k2);
					ans[now_x][now_y+1] = (r3|k3);
					--nowscore;
					return 1;
				}
			}
		}
		--tile_count[ans[now_x][now_y]];
		--tile_count[ans[now_x][now_y+1]];
		return 0;
	}
	
	bool vertical(int now_x , int now_y){	//縦線から横方向に伸ばす
		int w0 = code[ans[now_x][now_y]>>2]^2;
		int w3 = code[ans[now_x+1][now_y]>>2]^8;
		int c0 = ans[now_x+dx[lg[w0]]][now_y+dy[lg[w0]]]&3;
		int c3 = ans[now_x+1+dx[lg[w3]]][now_y+dy[lg[w3]]]&3;
		++tile_count[ans[now_x][now_y]];
		++tile_count[ans[now_x+1][now_y]];
		if((!~ans[now_x][now_y+1]) && (!~ans[now_x+1][now_y+1])){
			int k1 = xor128()%color_num , k2 = xor128()%(color_num-1);
			if(k2 >= k1) ++k2;
			if(tile_count[4|k1] && tile_count[8|k2]){
				int k0 = -1 , k3 = -1;
				int r0 = decode[1|w0]<<2 , r3 = decode[1|w3]<<2;
				repp(t,0,color_num) if(t != c0 && t != k1){
					if((k0<0 && tile_count[r0|t]) || (k0>=0 && tile_count[r0|k0] < tile_count[r0|t])) k0 = t;
				}
				repp(t,0,color_num) if(t != c3 && t != k2){
					if((k3<0 && tile_count[r3|t]+((r3|t)==(r0|k0)?-1:0)) || (k3>=0 && tile_count[r3|k3] < tile_count[r3|t]+((r3|t)==(r0|k0)?-1:0))) k3 = t;
				}
				if((~k0) && (~k3) && rnd_accept()){
					--tile_count[r0|k0];
					--tile_count[4|k1];
					--tile_count[8|k2];
					--tile_count[r3|k3];
					ans[now_x][now_y] = (r0|k0);
					ans[now_x][now_y+1] = (4|k1);
					ans[now_x+1][now_y+1] = (8|k2);
					ans[now_x+1][now_y] = (r3|k3);
					--nowscore;
					return 1;
				}
			}
		}
		if((!~ans[now_x][now_y-1]) && (!~ans[now_x+1][now_y-1])){
			int k1 = xor128()%color_num , k2 = xor128()%(color_num-1);
			if(k2 >= k1) ++k2;
			if(tile_count[k1] && tile_count[12|k2]){
				int k0 = -1 , k3 = -1;
				int r0 = decode[4|w0]<<2 , r3 = decode[4|w3]<<2;
				repp(t,0,color_num) if(t != c0 && t != k1){
					if((k0<0 && tile_count[r0|t]) || (k0>=0 && tile_count[r0|k0] < tile_count[r0|t])) k0 = t;
				}
				repp(t,0,color_num) if(t != c3 && t != k2){
					if((k3<0 && tile_count[r3|t]+((r3|t)==(r0|k0)?-1:0)) || (k3>=0 && tile_count[r3|k3] < tile_count[r3|t]+((r3|t)==(r0|k0)?-1:0))) k3 = t;
				}
				if((~k0) && (~k3) && rnd_accept()){
					--tile_count[r0|k0];
					--tile_count[k1];
					--tile_count[12|k2];
					--tile_count[r3|k3];
					ans[now_x][now_y] = (r0|k0);
					ans[now_x][now_y-1] = k1;
					ans[now_x+1][now_y-1] = (12|k2);
					ans[now_x+1][now_y] = (r3|k3);
					--nowscore;
					return 1;
				}
			}
		}
		--tile_count[ans[now_x][now_y]];
		--tile_count[ans[now_x+1][now_y]];
		return 0;
	}
	
	void solve0(){	//右下に最小の四角を構成
		int now_x = H-1 , now_y = W-1;
		int z0 = -1 , z1 = -1 , z2 = -1 , z3 = -1;
		repp(i,0,4) if((z0<0 && tile_count[i]) || (z0>=0 && tile_count[z0] < tile_count[i])) z0 = i;
		ans[now_x][now_y] = z0;
		if(~z0) --tile_count[z0];
		repp(i,0,4) if(i != z0 && ((z1<0 && tile_count[4|i]) || (z1>=0 && tile_count[4|z1] < tile_count[4|i]))) z1 = i;
		ans[now_x][now_y+1] = (4|z1);
		if(~z1) --tile_count[4|z1];
		repp(i,0,4) if(i != z0 && ((z3<0 && tile_count[12|i]) || (z3>=0 && tile_count[12|z3] < tile_count[12|i]))) z3 = i;
		ans[now_x+1][now_y] = (12|z3);
		if(~z3) --tile_count[12|z3];
		repp(i,0,4) if(i != z1 && i != z3 && ((z2<0 && tile_count[8|i]) || (z2>=0 && tile_count[8|z2] < tile_count[8|i]))) z2 = i;
		ans[now_x+1][now_y+1] = (8|z2);
		if(~z2) --tile_count[8|z2];
	}
	
	bool solve0_2(){
		if(h_max-h_min<2 || w_max-w_min<4) return 0;
		repm(i,h_max-1,h_min){
			repp(t,20,24) if((ans[i+1][w_max]&3) != (t&3) && ((ans[i][w_max]<0 && tile_count[t]) || (ans[i][w_max]>=0 && tile_count[ans[i][w_max]] < tile_count[t]))) ans[i][w_max] = t;
			if(!~ans[i][w_max]) return 0;
			--tile_count[ans[i][w_max]];
		}
		repp(t,4,8) if((ans[h_min+1][w_max]&3) != (t&3) && ((ans[h_min][w_max]<0 && tile_count[t]) || (ans[h_min][w_max]>=0 && tile_count[ans[h_min][w_max]] < tile_count[t]))) ans[h_min][w_max] = t;
		if(!~ans[h_min][w_max]) return 0;
		--tile_count[ans[h_min][w_max]];
		repm(j,w_max-1,w_min){
			repp(t,16,20) if((ans[h_min][j+1]&3) != (t&3) && ((ans[h_min][j]<0 && tile_count[t]) || (ans[h_min][j]>=0 && tile_count[ans[h_min][j]] < tile_count[t]))) ans[h_min][j] = t;
			if(!~ans[h_min][j]) return 0;
			--tile_count[ans[h_min][j]];
		}
		repp(t,0,4) if((ans[h_min][w_min+1]&3) != (t&3) && ((ans[h_min][w_min]<0 && tile_count[t]) || (ans[h_min][w_min]>=0 && tile_count[ans[h_min][w_min]] < tile_count[t]))) ans[h_min][w_min] = t;
		if(!~ans[h_min][w_min]) return 0;
		--tile_count[ans[h_min][w_min]];
		{
			int i = h_min+1;
			int j = w_min+2;
			while(i<h_max-1){
				repp(t,12,16) if((ans[i-1][w_min]&3) != (t&3) && ((ans[i][w_min]<0 && tile_count[t]) || (ans[i][w_min]>=0 && tile_count[ans[i][w_min]] < tile_count[t]))) ans[i][w_min] = t;
				if(!~ans[i][w_min]) return 0;
				--tile_count[ans[i][w_min]];
				repp(t,4,8) if((ans[i][w_min]&3) != (t&3) && ((ans[i][w_min+1]<0 && tile_count[t]) || (ans[i][w_min+1]>=0 && tile_count[ans[i][w_min+1]] < tile_count[t]))) ans[i][w_min+1] = t;
				if(!~ans[i][w_min+1]) return 0;
				--tile_count[ans[i][w_min+1]];
				++i;
				repp(t,8,12) if((ans[i-1][w_min+1]&3) != (t&3) && ((ans[i][w_min+1]<0 && tile_count[t]) || (ans[i][w_min+1]>=0 && tile_count[ans[i][w_min+1]] < tile_count[t]))) ans[i][w_min+1] = t;
				if(!~ans[i][w_min+1]) return 0;
				--tile_count[ans[i][w_min+1]];
				repp(t,0,4) if((ans[i][w_min+1]&3) != (t&3) && ((ans[i][w_min]<0 && tile_count[t]) || (ans[i][w_min]>=0 && tile_count[ans[i][w_min]] < tile_count[t]))) ans[i][w_min] = t;
				if(!~ans[i][w_min]) return 0;
				--tile_count[ans[i][w_min]];
				++i;
			}
			if(i == h_max){
				repp(t,12,16) if((ans[i-1][w_min]&3) != (t&3) && ((ans[i][w_min]<0 && tile_count[t]) || (ans[i][w_min]>=0 && tile_count[ans[i][w_min]] < tile_count[t]))) ans[i][w_min] = t;
				if(!~ans[i][w_min]) return 0;
				--tile_count[ans[i][w_min]];
				repp(t,16,20) if((ans[i][w_min]&3) != (t&3) && ((ans[i][w_min+1]<0 && tile_count[t]) || (ans[i][w_min+1]>=0 && tile_count[ans[i][w_min+1]] < tile_count[t]))) ans[i][w_min+1] = t;
				if(!~ans[i][w_min+1]) return 0;
				--tile_count[ans[i][w_min+1]];
			} else {
				repp(t,20,24) if((ans[i-1][w_min]&3) != (t&3) && ((ans[i][w_min]<0 && tile_count[t]) || (ans[i][w_min]>=0 && tile_count[ans[i][w_min]] < tile_count[t]))) ans[i][w_min] = t;
				if(!~ans[i][w_min]) return 0;
				--tile_count[ans[i][w_min]];
				++i;
				repp(t,12,16) if((ans[i-1][w_min]&3) != (t&3) && ((ans[i][w_min]<0 && tile_count[t]) || (ans[i][w_min+1]>=0 && tile_count[ans[i][w_min]] < tile_count[t]))) ans[i][w_min] = t;
				if(!~ans[i][w_min]) return 0;
				--tile_count[ans[i][w_min]];
				--j;
			}
			while(j<w_max-3){
				repp(t,8,12) if((ans[h_max][j-1]&3) != (t&3) && ((ans[h_max][j]<0 && tile_count[t]) || (ans[h_max][j]>=0 && tile_count[ans[h_max][j]] < tile_count[t]))) ans[h_max][j] = t;
				if(!~ans[h_max][j]) return 0;
				--tile_count[ans[h_max][j]];
				repp(t,0,4) if((ans[h_max][j]&3) != (t&3) && ((ans[h_max-1][j]<0 && tile_count[t]) || (ans[h_max-1][j]>=0 && tile_count[ans[h_max-1][j]] < tile_count[t]))) ans[h_max-1][j] = t;
				if(!~ans[h_max-1][j]) return 0;
				--tile_count[ans[h_max-1][j]];
				++j;
				repp(t,4,8) if((ans[h_max-1][j-1]&3) != (t&3) && ((ans[h_max-1][j]<0 && tile_count[t]) || (ans[h_max-1][j]>=0 && tile_count[ans[h_max-1][j]] < tile_count[t]))) ans[h_max-1][j] = t;
				if(!~ans[h_max-1][j]) return 0;
				--tile_count[ans[h_max-1][j]];
				repp(t,12,16) if((ans[h_max-1][j]&3) != (t&3) && ((ans[h_max][j]<0 && tile_count[t]) || (ans[h_max][j]>=0 && tile_count[ans[h_max][j]] < tile_count[t]))) ans[h_max][j] = t;
				if(!~ans[h_max][j]) return 0;
				--tile_count[ans[h_max][j]];
				++j;
			}
			if(j==w_max-3){
				repp(t,16,20) if((ans[h_max][j-1]&3) != (t&3) && ((ans[h_max][j]<0 && tile_count[t]) || (ans[h_max][j]>=0 && tile_count[ans[h_max][j]] < tile_count[t]))) ans[h_max][j] = t;
				if(!~ans[h_max][j]) return 0;
				--tile_count[ans[h_max][j]];
				++j;
			}
			repp(t,8,12) if((ans[h_max][j-1]&3) != (t&3) && ((ans[h_max][j]<0 && tile_count[t]) || (ans[h_max][j]>=0 && tile_count[ans[h_max][j]] < tile_count[t]))) ans[h_max][j] = t;
			if(!~ans[h_max][j]) return 0;
			--tile_count[ans[h_max][j]];
		}
		repp(t0,0,4) if((ans[h_max][w_max-2]&3) != t0 && tile_count[t0]){
			repp(t1,0,4) if((ans[h_max][w_max-1]&3) != t1 && t0 != t1 && tile_count[4|t1]){
				ans[h_max-1][w_max-2] = t0;
				ans[h_max-1][w_max-1] = (4|t1);
				--tile_count[t0];
				--tile_count[4|t1];
				return 1;
			}
		}
		return 0;
	}
	
	bool solve3(){
		if(h_max-h_min<4 || w_max-w_min<4) return 0;
		int x = h_max - 1 , y = w_max;
		while(x > h_min+1){
			repp(t,4,8) if((ans[x+1][y]&3) != (t&3) && ((ans[x][y]<0 && tile_count[t]) || (ans[x][y]>=0 && tile_count[ans[x][y]] < tile_count[t]))) ans[x][y] = t;
			if(!~ans[x][y]) return 0;
			--tile_count[ans[x][y]];
			repp(t,12,16) if((ans[x][y]&3) != (t&3) && ((ans[x][y-1]<0 && tile_count[t]) || (ans[x][y-1]>=0 && tile_count[ans[x][y-1]] < tile_count[t]))) ans[x][y-1] = t;
			if(!~ans[x][y-1]) return 0;
			--tile_count[ans[x][y-1]];
			--x;
			repp(t,0,4) if((ans[x+1][y-1]&3) != (t&3) && ((ans[x][y-1]<0 && tile_count[t]) || (ans[x][y-1]>=0 && tile_count[ans[x][y-1]] < tile_count[t]))) ans[x][y-1] = t;
			if(!~ans[x][y-1]) return 0;
			--tile_count[ans[x][y-1]];
			repp(t,8,12) if((ans[x][y-1]&3) != (t&3) && ((ans[x][y]<0 && tile_count[t]) || (ans[x][y]>=0 && tile_count[ans[x][y]] < tile_count[t]))) ans[x][y] = t;
			if(!~ans[x][y]) return 0;
			--tile_count[ans[x][y]];
			--x;
		}
		if(x == h_min){
			repp(t,4,8) if((ans[x+1][y]&3) != (t&3) && ((ans[x][y]<0 && tile_count[t]) || (ans[x][y]>=0 && tile_count[ans[x][y]] < tile_count[t]))) ans[x][y] = t;
			if(!~ans[x][y]) return 0;
			--tile_count[ans[x][y]];
			--y;
			repp(t,16,20) if((ans[x][y+1]&3) != (t&3) && ((ans[x][y]<0 && tile_count[t]) || (ans[x][y]>=0 && tile_count[ans[x][y]] < tile_count[t]))) ans[x][y] = t;
			if(!~ans[x][y]) return 0;
			--tile_count[ans[x][y]];
			--y;
		} else {
			repp(t,20,24) if((ans[x+1][y]&3) != (t&3) && ((ans[x][y]<0 && tile_count[t]) || (ans[x][y]>=0 && tile_count[ans[x][y]] < tile_count[t]))) ans[x][y] = t;
			if(!~ans[x][y]) return 0;
			--tile_count[ans[x][y]];
			--x;
			repp(t,4,8) if((ans[x+1][y]&3) != (t&3) && ((ans[x][y]<0 && tile_count[t]) || (ans[x][y]>=0 && tile_count[ans[x][y]] < tile_count[t]))) ans[x][y] = t;
			if(!~ans[x][y]) return 0;
			--tile_count[ans[x][y]];
			--y;
		}
		while(y > w_min+1){
			repp(t,0,4) if((ans[x][y+1]&3) != (t&3) && ((ans[x][y]<0 && tile_count[t]) || (ans[x][y]>=0 && tile_count[ans[x][y]] < tile_count[t]))) ans[x][y] = t;
			if(!~ans[x][y]) return 0;
			--tile_count[ans[x][y]];
			repp(t,8,12) if((ans[x][y]&3) != (t&3) && ((ans[x+1][y]<0 && tile_count[t]) || (ans[x+1][y]>=0 && tile_count[ans[x+1][y]] < tile_count[t]))) ans[x+1][y] = t;
			if(!~ans[x+1][y]) return 0;
			--tile_count[ans[x+1][y]];
			--y;
			repp(t,12,16) if((ans[x+1][y+1]&3) != (t&3) && ((ans[x+1][y]<0 && tile_count[t]) || (ans[x+1][y]>=0 && tile_count[ans[x+1][y]] < tile_count[t]))) ans[x+1][y] = t;
			if(!~ans[x+1][y]) return 0;
			--tile_count[ans[x+1][y]];
			repp(t,4,8) if((ans[x+1][y]&3) != (t&3) && ((ans[x][y]<0 && tile_count[t]) || (ans[x][y]>=0 && tile_count[ans[x][y]] < tile_count[t]))) ans[x][y] = t;
			if(!~ans[x][y]) return 0;
			--tile_count[ans[x][y]];
			--y;
		}
		if(y == w_min){
			repp(t,0,4) if((ans[x][y+1]&3) != (t&3) && ((ans[x][y]<0 && tile_count[t]) || (ans[x][y]>=0 && tile_count[ans[x][y]] < tile_count[t]))) ans[x][y] = t;
			if(!~ans[x][y]) return 0;
			--tile_count[ans[x][y]];
			++x;
			repp(t,20,24) if((ans[x-1][y]&3) != (t&3) && ((ans[x][y]<0 && tile_count[t]) || (ans[x][y]>=0 && tile_count[ans[x][y]] < tile_count[t]))) ans[x][y] = t;
			if(!~ans[x][y]) return 0;
			--tile_count[ans[x][y]];
			++x;
		} else {
			repp(t,16,20) if((ans[x][y+1]&3) != (t&3) && ((ans[x][y]<0 && tile_count[t]) || (ans[x][y]>=0 && tile_count[ans[x][y]] < tile_count[t]))) ans[x][y] = t;
			if(!~ans[x][y]) return 0;
			--tile_count[ans[x][y]];
			--y;
			repp(t,0,4) if((ans[x][y+1]&3) != (t&3) && ((ans[x][y]<0 && tile_count[t]) || (ans[x][y]>=0 && tile_count[ans[x][y]] < tile_count[t]))) ans[x][y] = t;
			if(!~ans[x][y]) return 0;
			--tile_count[ans[x][y]];
			++x;
		}
		while(x < h_max-1){
			repp(t,12,16) if((ans[x-1][y]&3) != (t&3) && ((ans[x][y]<0 && tile_count[t]) || (ans[x][y]>=0 && tile_count[ans[x][y]] < tile_count[t]))) ans[x][y] = t;
			if(!~ans[x][y]) return 0;
			--tile_count[ans[x][y]];
			repp(t,4,8) if((ans[x][y]&3) != (t&3) && ((ans[x][y+1]<0 && tile_count[t]) || (ans[x][y+1]>=0 && tile_count[ans[x][y+1]] < tile_count[t]))) ans[x][y+1] = t;
			if(!~ans[x][y+1]) return 0;
			--tile_count[ans[x][y+1]];
			++x;
			repp(t,8,12) if((ans[x-1][y+1]&3) != (t&3) && ((ans[x][y+1]<0 && tile_count[t]) || (ans[x][y+1]>=0 && tile_count[ans[x][y+1]] < tile_count[t]))) ans[x][y+1] = t;
			if(!~ans[x][y+1]) return 0;
			--tile_count[ans[x][y+1]];
			repp(t,0,4) if((ans[x][y+1]&3) != (t&3) && ((ans[x][y]<0 && tile_count[t]) || (ans[x][y]>=0 && tile_count[ans[x][y]] < tile_count[t]))) ans[x][y] = t;
			if(!~ans[x][y]) return 0;
			--tile_count[ans[x][y]];
			++x;
		}
		if(x == h_max){
			repp(t,12,16) if((ans[x-1][y]&3) != (t&3) && ((ans[x][y]<0 && tile_count[t]) || (ans[x][y]>=0 && tile_count[ans[x][y]] < tile_count[t]))) ans[x][y] = t;
			if(!~ans[x][y]) return 0;
			--tile_count[ans[x][y]];
			++y;
			repp(t,16,20) if((ans[x][y-1]&3) != (t&3) && ((ans[x][y]<0 && tile_count[t]) || (ans[x][y]>=0 && tile_count[ans[x][y]] < tile_count[t]))) ans[x][y] = t;
			if(!~ans[x][y]) return 0;
			--tile_count[ans[x][y]];
			++y;
		} else {
			repp(t,20,24) if((ans[x-1][y]&3) != (t&3) && ((ans[x][y]<0 && tile_count[t]) || (ans[x][y]>=0 && tile_count[ans[x][y]] < tile_count[t]))) ans[x][y] = t;
			if(!~ans[x][y]) return 0;
			--tile_count[ans[x][y]];
			++x;
			repp(t,12,16) if((ans[x-1][y]&3) != (t&3) && ((ans[x][y]<0 && tile_count[t]) || (ans[x][y]>=0 && tile_count[ans[x][y]] < tile_count[t]))) ans[x][y] = t;
			if(!~ans[x][y]) return 0;
			--tile_count[ans[x][y]];
			++y;
		}
		while(y < w_max - 1){
			repp(t,8,12) if((ans[x][y-1]&3) != (t&3) && ((ans[x][y]<0 && tile_count[t]) || (ans[x][y]>=0 && tile_count[ans[x][y]] < tile_count[t]))) ans[x][y] = t;
			if(!~ans[x][y]) return 0;
			--tile_count[ans[x][y]];
			repp(t,0,4) if((ans[x][y]&3) != (t&3) && ((ans[x-1][y]<0 && tile_count[t]) || (ans[x-1][y]>=0 && tile_count[ans[x-1][y]] < tile_count[t]))) ans[x-1][y] = t;
			if(!~ans[x-1][y]) return 0;
			--tile_count[ans[x-1][y]];
			++y;
			repp(t,4,8) if((ans[x-1][y-1]&3) != (t&3) && ((ans[x-1][y]<0 && tile_count[t]) || (ans[x-1][y]>=0 && tile_count[ans[x-1][y]] < tile_count[t]))) ans[x-1][y] = t;
			if(!~ans[x-1][y]) return 0;
			--tile_count[ans[x-1][y]];
			repp(t,12,16) if((ans[x-1][y]&3) != (t&3) && ((ans[x][y]<0 && tile_count[t]) || (ans[x][y]>=0 && tile_count[ans[x][y]] < tile_count[t]))) ans[x][y] = t;
			if(!~ans[x][y]) return 0;
			--tile_count[ans[x][y]];
			++y;
		}
		return 1;
	}
	
	bool solve4_h(){
		{
			int c0 = -1 , c1 = -1;
			repp(t,20,24) if((ans[h_max+2][w_max-1]&3) != (t&3) && ((c0<0 && tile_count[t]) || (c0>=0 && tile_count[c0] < tile_count[t]))) c0 = t;
			if(!~c0) return 0;
			++tile_count[ans[h_max+1][w_max-1]];
			ans[h_max+1][w_max-1] = c0;
			--tile_count[c0];
			repp(t,20,24) if((ans[h_max+2][w_max]&3) != (t&3) && ((c1<0 && tile_count[t]) || (c1>=0 && tile_count[c1] < tile_count[t]))) c1 = t;
			if(!~c1) return 0;
			++tile_count[ans[h_max+1][w_max]];
			ans[h_max+1][w_max] = c1;
			--tile_count[c1];
		}
		repm(i,h_max,h_min){
			int c0 = -1 , c1 = -1;
			repp(t,20,24) if((ans[i+1][w_max-1]&3) != (t&3) && ((c0<0 && tile_count[t]) || (c0>=0 && tile_count[c0] < tile_count[t]))) c0 = t;
			if(!~c0) return 0;
			ans[i][w_max-1] = c0;
			--tile_count[c0];
			repp(t,20,24) if((ans[i+1][w_max]&3) != (t&3) && ((c1<0 && tile_count[t]) || (c1>=0 && tile_count[c1] < tile_count[t]))) c1 = t;
			if(!~c1) return 0;
			ans[i][w_max] = c1;
			--tile_count[c1];
		}
		{
			int c0 = -1 , c1 = -1;
			repp(t,0,4) if((ans[h_min+1][w_max-1]&3) != (t&3) && ((c0<0 && tile_count[t]) || (c0>=0 && tile_count[c0] < tile_count[t]))) c0 = t;
			if(!~c0) return 0;
			ans[h_min][w_max-1] = c0;
			--tile_count[c0];
			repp(t,4,8) if((ans[h_min+1][w_max]&3) != (t&3) && (c0&3) != (t&3) && ((c1<0 && tile_count[t]) || (c1>=0 && tile_count[c1] < tile_count[t]))) c1 = t;
			if(!~c1) return 0;
			ans[h_min][w_max] = c1;
			--tile_count[c1];
		}
		w_max -= 2;
		return 1;
	}
	
	bool solve4_w(){
		{
			int c0 = -1 , c1 = -1;
			repp(t,16,20) if((ans[h_min][w_min-2]&3) != (t&3) && ((c0<0 && tile_count[t]) || (c0>=0 && tile_count[c0] < tile_count[t]))) c0 = t;
			if(!~c0) return 0;
			++tile_count[ans[h_min][w_min-1]];
			ans[h_min][w_min-1] = c0;
			--tile_count[c0];
			repp(t,16,20) if((ans[h_min+1][w_min-2]&3) != (t&3) && ((c1<0 && tile_count[t]) || (c1>=0 && tile_count[c1] < tile_count[t]))) c1 = t;
			if(!~c1) return 0;
			++tile_count[ans[h_min+1][w_min-1]];
			ans[h_min+1][w_min-1] = c1;
			--tile_count[c1];
		}
		repp(j,w_min,w_max){
			int c0 = -1 , c1 = -1;
			repp(t,16,20) if((ans[h_min][j-1]&3) != (t&3) && ((c0<0 && tile_count[t]) || (c0>=0 && tile_count[c0] < tile_count[t]))) c0 = t;
			if(!~c0) return 0;
			ans[h_min][j] = c0;
			--tile_count[c0];
			repp(t,16,20) if((ans[h_min+1][j-1]&3) != (t&3) && ((c1<0 && tile_count[t]) || (c1>=0 && tile_count[c1] < tile_count[t]))) c1 = t;
			if(!~c1) return 0;
			ans[h_min+1][j] = c1;
			--tile_count[c1];
		}
		{
			int c0 = -1 , c1 = -1;
			repp(t,4,8) if((ans[h_min][w_max-1]&3) != (t&3) && ((c0<0 && tile_count[t]) || (c0>=0 && tile_count[c0] < tile_count[t]))) c0 = t;
			if(!~c0) return 0;
			ans[h_min][w_max] = c0;
			--tile_count[c0];
			repp(t,8,12) if((ans[h_min+1][w_max-1]&3) != (t&3) && (c0&3) != (t&3) && ((c1<0 && tile_count[t]) || (c1>=0 && tile_count[c1] < tile_count[t]))) c1 = t;
			if(!~c1) return 0;
			ans[h_min+1][w_max] = c1;
			--tile_count[c1];
		}
		h_min += 2;
		return 1;
	}
	
	void solveA(){
		double end_time = get_time() + MAX_TIME;
		solve0();
		for(int i = 0 ; ; ++i){
			memcpy(ini,ans,MC*MC);
			memcpy(ini_tile_count,tile_count,NT*4);
			if(i){
				int c0 = -1 , c1 = -1 , c2 = -1 , c3 = -1;
				repp(t0,20,24) if((ans[H+2-i*2][W-i-1]&3) != (t0&3) && ((c0<0 && tile_count[t0]) || (c0>=0 && tile_count[c0] < tile_count[t0]))) c0 = t0;
				repp(t1,20,24) if((ans[H+2-i*2][W-i]&3) != (t1&3) && ((c1<0 && tile_count[t1]+(c0==t1?-1:0)) || (c1>=0 && tile_count[c1] < tile_count[t1]+(c0==t1?-1:0)))) c1 = t1;
				repp(t2,20,24) if((c0&3) != (t2&3) && ((c2<0 && tile_count[t2]+(c0==t2?-1:0)+(c1==t2?-1:0)) || (c2>=0 && tile_count[c2] < tile_count[t2]+(c0==t2?-1:0)+(c1==t2?-1:0)))) c2 = t2;
				repp(t3,20,24) if((c1&3) != (t3&3) && ((c3<0 && tile_count[t3]+(c0==t3?-1:0)+(c1==t3?-1:0)+(c2==t3?-1:0)) || (c3>=0 && tile_count[c3] < tile_count[t3]+(c0==t3?-1:0)+(c1==t3?-1:0)+(c2==t3?-1:0)))) c3 = t3;
				if((~c0) && (~c1) && (~c2) && (~c3)){
					++tile_count[ans[H+1-i*2][W-i-1]];
					++tile_count[ans[H+1-i*2][W-i]];
					ans[H+1-i*2][W-i-1] = c0;
					ans[H+1-i*2][W-i] = c1;
					ans[H-i*2][W-i-1] = c2;
					ans[H-i*2][W-i] = c3;
					--tile_count[c0];
					--tile_count[c1];
					--tile_count[c2];
					--tile_count[c3];
				} else {
					break;
				}
			} else {
				++tile_count[ans[H-1][W]];
				++tile_count[ans[H-1][W-1]];
				ans[H-1][W] = -1;
				ans[H-1][W-1] = -1;
			}
			h_min = 1+i; h_max = H-i*2;
			w_min = 1+i*2; w_max = W-i;
			if(!solve0_2()) break;
		}
		h_min = max(1,h_min-1); h_max = min(H,h_max+1);
		w_min = max(1,w_min-1); w_max = min(W,w_max+1);
		memcpy(ans,ini,MC*MC);
		memcpy(tile_count,ini_tile_count,NT*4);
		int iniscore = 0;
		repp(i,0,NT) iniscore += tile_count[i];
		iniscore /= 2;
		while(get_time() < end_time){
			nowscore = iniscore;
			solve1();
			if(bestscore > nowscore){
				memcpy(best,ans,MC*MC);
				bestscore = nowscore;
			}
			memcpy(tile_count,ini_tile_count,NT*4);
			memcpy(ans,ini,MC*MC);
		}
	}
	
	void solveB(){
		double end_time = get_time() + MAX_TIME;
		for(int i = 0 ; ; ++i){
			if(i){
				int c0 = -1;
				repp(t,20,24) if((ans[h_max+2][w_max]&3) != (t&3) && ((c0<0 && tile_count[t]) || (c0>=0 && tile_count[c0] < tile_count[t]))) c0 = t;
				if(!~c0) break;
				++tile_count[ans[h_max+1][w_max]];
				ans[h_max+1][w_max] = c0;
				--tile_count[c0];
				int c1 = -1;
				repp(t,20,24) if((ans[h_max+2][w_max-1]&3) != (t&3) && ((c1<0 && tile_count[t]) || (c1>=0 && tile_count[c1] < tile_count[t]))) c1 = t;
				if(!~c1) break;
				++tile_count[ans[h_max+1][w_max-1]];
				ans[h_max+1][w_max-1] = c1;
				--tile_count[c1];
				int c2 = -1;
				repp(t,20,24) if((ans[h_max+1][w_max]&3) != (t&3) && ((c2<0 && tile_count[t]) || (c2>=0 && tile_count[c1] < tile_count[t]))) c2 = t;
				if(!~c2) break;
				ans[h_max][w_max] = c2;
				--tile_count[c2];
			} else {
				repp(t,8,12) if((ans[H][W]<0 && tile_count[t]) || (ans[H][W]>=0 && tile_count[ans[H][W]] < tile_count[t])) ans[H][W] = t;
				--tile_count[ans[H][W]];
			}
			if(solve3()){
				if(i){
					int c0 = -1;
					repp(t,4,8) if((ans[h_max][w_max-2]&3) != (t&3) && (ans[h_max+1][w_max-1]&3) != (t&3) && ((c0<0 && tile_count[t]) || (c0>=0 && tile_count[c0] < tile_count[t]))) c0 = t;
					if(!~c0) break;
					ans[h_max][w_max-1] = c0;
					--tile_count[c0];
				} else {
					int c0 = -1;
					repp(t,16,20) if((ans[h_max][w_max-2]&3) != (t&3) && (ans[h_max][w_max]&3) != (t&3) && ((c0<0 && tile_count[t]) || (c0>=0 && tile_count[c0] < tile_count[t]))) c0 = t;
					if(!~c0) break;
					ans[h_max][w_max-1] = c0;
					--tile_count[c0];
				}
			} else {
				if(!i){
					repp(i,0,NT) tile_count[i] = tile[i].size();
					repp(i,1,H+1) fill(ans[i]+1,ans[i]+W+1,-1);
					solve0();
					memcpy(ini,ans,MC*MC);
					memcpy(ini_tile_count,tile_count,NT*4);
				}
				break;
			}
			memcpy(ini,ans,MC*MC);
			memcpy(ini_tile_count,tile_count,NT*4);
			h_min += 2; h_max -= 2;
			w_min += 2; w_max -= 2;
		}
		
		memcpy(ans,ini,MC*MC);
		memcpy(tile_count,ini_tile_count,NT*4);
		if(~ans[1][1]){
			bool b = 1;
			if((h_max-h_min)%2==0 && (w_max-w_min)%2==0){
				repp(i,4,6){
					int z = tile_count[i<<2];
					wire_count[i] = z;
					repp(j,1,4){
						wire_count[i] += tile_count[(i<<2)|j];
						z = max(z,tile_count[(i<<2)|j]);
					}
					wire_count[i] = min(wire_count[i],(wire_count[i]-z)*2) - 4;
				}
				int dh = h_max - h_min + 1 , dw = w_max - w_min + 1;
				int x = 0 , y = 0 , z = max(dh,dw);
				for(int i = 2 ; i < dh ; i += 2){
					if(dh-2*i<0) break;
					int p = dw - wire_count[4] / (2*i) + 1;
					int q = wire_count[5] / (2*(dh-i)) + 1;
					repp(j,p,q){
						if(dw-2*j<0) break;
						if(j<0) j = -1;
						if(j&1) continue;
						if(z > max(abs(dh-2*i),abs(dw-2*j))){
							x = i;
							y = j;
							z = max(abs(dh-2*i),abs(dw-2*j));
						}
					}
				}
				for(int j = 0 ; j < y ; j += 2){
					++tile_count[ans[h_min-1][w_min+j]];
					++tile_count[ans[h_min-1][w_min+j+1]];
					++tile_count[ans[h_max+1][w_max-j]];
					++tile_count[ans[h_max+1][w_max-j-1]];
					bool b = 1;
					repp(i,0,dh-x){
						int c0 = -1 , c1 = -1;
						repp(t,20,24) if((ans[h_min+i-2][w_min+j]&3) != (t&3) && ((c0<0 && tile_count[t]) || (c0>=0 && tile_count[c0] < tile_count[t]))) c0 = t;
						if(!~c0){ b = 0; break;}
						ans[h_min+i-1][w_min+j] = c0;
						--tile_count[c0];
						repp(t,20,24) if((ans[h_min+i-2][w_min+j+1]&3) != (t&3) && ((c1<0 && tile_count[t]) || (c1>=0 && tile_count[c1] < tile_count[t]))) c1 = t;
						if(!~c1){ b = 0; break;}
						ans[h_min+i-1][w_min+j+1] = c1;
						--tile_count[c1];
						c0 = -1; c1 = -1;
						repp(t,20,24) if((ans[h_max-i+2][w_max-j]&3) != (t&3) && ((c0<0 && tile_count[t]) || (c0>=0 && tile_count[c0] < tile_count[t]))) c0 = t;
						if(!~c0){ b = 0; break;}
						ans[h_max-i+1][w_max-j] = c0;
						--tile_count[c0];
						repp(t,20,24) if((ans[h_max-i+2][w_max-j-1]&3) != (t&3) && ((c1<0 && tile_count[t]) || (c1>=0 && tile_count[c1] < tile_count[t]))) c1 = t;
						if(!~c1){ b = 0; break;}
						ans[h_max-i+1][w_max-j-1] = c1;
						--tile_count[c1];
					}
					if(!b) break;
					int c0 = -1 , c1 = -1;
					repp(t,12,16) if((ans[h_max-x-1][w_min+j]&3) != (t&3) && ((c0<0 && tile_count[t]) || (c0>=0 && tile_count[c0] < tile_count[t]))) c0 = t;
					if(!~c0) break;
					ans[h_max-x][w_min+j] = c0;
					--tile_count[c0];
					repp(t,8,12) if((ans[h_max-x-1][w_min+j+1]&3) != (t&3) && (c0&3) != (t&3) && ((c1<0 && tile_count[t]) || (c1>=0 && tile_count[c1] < tile_count[t]))) c1 = t;
					if(!~c1) break;
					ans[h_max-x][w_min+j+1] = c1;
					--tile_count[c1];
					c0 = -1; c1 = -1;
					repp(t,4,8) if((ans[h_min+x+1][w_max-j]&3) != (t&3) && ((c0<0 && tile_count[t]) || (c0>=0 && tile_count[c0] < tile_count[t]))) c0 = t;
					if(!~c0) break;
					ans[h_min+x][w_max-j] = c0;
					--tile_count[c0];
					repp(t,0,4) if((ans[h_min+x+1][w_max-j-1]&3) != (t&3) && (c0&3) != (t&3) && ((c1<0 && tile_count[t]) || (c1>=0 && tile_count[c1] < tile_count[t]))) c1 = t;
					if(!~c1) break;
					ans[h_min+x][w_max-j-1] = c1;
					--tile_count[c1];
					memcpy(ini,ans,MC*MC);
					memcpy(ini_tile_count,tile_count,NT*4);
				}
				memcpy(ans,ini,MC*MC);
				memcpy(tile_count,ini_tile_count,NT*4);
				for(int i = 0 ; i < x ; i += 2){
					++tile_count[ans[h_min+i][w_max+1]];
					++tile_count[ans[h_min+i+1][w_max+1]];
					++tile_count[ans[h_max-i][w_min-1]];
					++tile_count[ans[h_max-i-1][w_min-1]];
					bool b = 1;
					repp(j,0,dw-y){
						int c0 = -1 , c1 = -1;
						repp(t,16,20) if((ans[h_min+i][w_max-j+2]&3) != (t&3) && ((c0<0 && tile_count[t]) || (c0>=0 && tile_count[c0] < tile_count[t]))) c0 = t;
						if(!~c0){ b = 0; break;}
						ans[h_min+i][w_max-j+1] = c0;
						--tile_count[c0];
						repp(t,16,20) if((ans[h_min+i+1][w_max-j+2]&3) != (t&3) && ((c1<0 && tile_count[t]) || (c1>=0 && tile_count[c1] < tile_count[t]))) c1 = t;
						if(!~c1){ b = 0; break;}
						ans[h_min+i+1][w_max-j+1] = c1;
						--tile_count[c1];
						c0 = -1; c1 = -1;
						repp(t,16,20) if((ans[h_max-i][w_min+j-2]&3) != (t&3) && ((c0<0 && tile_count[t]) || (c0>=0 && tile_count[c0] < tile_count[t]))) c0 = t;
						if(!~c0){ b = 0; break;}
						ans[h_max-i][w_min+j-1] = c0;
						--tile_count[c0];
						repp(t,16,20) if((ans[h_max-i-1][w_min+j-2]&3) != (t&3) && ((c1<0 && tile_count[t]) || (c1>=0 && tile_count[c1] < tile_count[t]))) c1 = t;
						if(!~c1){ b = 0; break;}
						ans[h_max-i-1][w_min+j-1] = c1;
						--tile_count[c1];
					}
					if(!b) break;
					int c0 = -1 , c1 = -1;
					repp(t,0,4) if((ans[h_min+i][w_min+y+1]&3) != (t&3) && ((c0<0 && tile_count[t]) || (c0>=0 && tile_count[c0] < tile_count[t]))) c0 = t;
					if(!~c0) break;
					ans[h_min+i][w_min+y] = c0;
					--tile_count[c0];
					repp(t,12,16) if((ans[h_min+i+1][w_min+y+1]&3) != (t&3) && (c0&3) != (t&3) && ((c1<0 && tile_count[t]) || (c1>=0 && tile_count[c1] < tile_count[t]))) c1 = t;
					if(!~c1) break;
					ans[h_min+i+1][w_min+y] = c1;
					--tile_count[c1];
					c0 = -1; c1 = -1;
					repp(t,8,12) if((ans[h_max-i][w_max-y-1]&3) != (t&3) && ((c0<0 && tile_count[t]) || (c0>=0 && tile_count[c0] < tile_count[t]))) c0 = t;
					if(!~c0) break;
					ans[h_max-i][w_max-y] = c0;
					--tile_count[c0];
					repp(t,4,8) if((ans[h_max-i-1][w_max-y-1]&3) != (t&3) && (c0&3) != (t&3) && ((c1<0 && tile_count[t]) || (c1>=0 && tile_count[c1] < tile_count[t]))) c1 = t;
					if(!~c1) break;
					ans[h_max-i-1][w_max-y] = c1;
					--tile_count[c1];
					memcpy(ini,ans,MC*MC);
					memcpy(ini_tile_count,tile_count,NT*4);
				}
				memcpy(ans,ini,MC*MC);
				memcpy(tile_count,ini_tile_count,NT*4);
			} else {
				if((h_max-h_min)%2==1 && (w_max-w_min)%2==1){
					for(int j = w_min ; j < w_max ; j += 2){
						int c0 = -1 , c1 = -1 , c2 = -1 , c3 = -1;
						repp(t,20,24) if((ans[h_min-2][j]&3) != (t&3) && ((c0<0 && tile_count[t]) || (c0>=0 && tile_count[c0] < tile_count[t]))) c0 = t;
						if(!~c0){ b = 0; break;}
						++tile_count[ans[h_min-1][j]];
						ans[h_min-1][j] = c0;
						--tile_count[c0];
						repp(t,20,24) if((ans[h_min-2][j+1]&3) != (t&3) && ((c1<0 && tile_count[t]) || (c1>=0 && tile_count[c1] < tile_count[t]))) c1 = t;
						if(!~c1){ b = 0; break;}
						++tile_count[ans[h_min-1][j+1]];
						ans[h_min-1][j+1] = c1;
						--tile_count[c1];
						repp(t,12,16) if((c0&3) != (t&3) && ((c2<0 && tile_count[t]) || (c2>=0 && tile_count[c2] < tile_count[t]))) c2 = t;
						if(!~c2){ b = 0; break;}
						++tile_count[ans[h_min][j]];
						ans[h_min][j] = c2;
						--tile_count[c2];
						repp(t,8,12) if((c1&3) != (t&3) && (c2&3) != (t&3) && ((c3<0 && tile_count[t]) || (c3>=0 && tile_count[c3] < tile_count[t]))) c3 = t;
						if(!~c3){ b = 0; break;}
						++tile_count[ans[h_min][j+1]];
						ans[h_min][j+1] = c3;
						--tile_count[c3];
					}
					if(b){
						memcpy(ini,ans,MC*MC);
						memcpy(ini_tile_count,tile_count,NT*4);
						++h_min;
					}
				}
				while(b){
					if(h_max - h_min < w_max - w_min){
						if(!solve4_h()){
							memcpy(ans,ini,MC*MC);
							memcpy(tile_count,ini_tile_count,NT*4);
							if(!solve4_w()) b = 0;
						}
					} else {
						if(!solve4_w()){
							memcpy(ans,ini,MC*MC);
							memcpy(tile_count,ini_tile_count,NT*4);
							if(!solve4_h()) b = 0;
						}
					}
					if(b){
						memcpy(ini,ans,MC*MC);
						memcpy(ini_tile_count,tile_count,NT*4);
					}
				}
			}
		}
		h_min = max(1,h_min-1); h_max = min(H,h_max+1);
		w_min = max(1,w_min-1); w_max = min(W,w_max+1);
		memcpy(ans,ini,MC*MC);
		memcpy(tile_count,ini_tile_count,NT*4);
		int iniscore = 0;
		repp(i,0,NT) iniscore += tile_count[i];
		iniscore /= 2;
		while(get_time() < end_time){
			nowscore = iniscore;
			solve1();
			if(bestscore > nowscore){
				memcpy(best,ans,MC*MC);
				bestscore = nowscore;
			}
			memcpy(tile_count,ini_tile_count,NT*4);
			memcpy(ans,ini,MC*MC);
		}
	}
	
	void solve1(){	//山登り
		int cnt = 0;
		while(cnt<30){
			bool b = 0;
			repp(i,h_min,h_max+1) repp(j,w_min,w_max+1) if(~ans[i][j]){
				if(code[ans[i][j]>>2]&1) b |= horizontal(i,j);
				if(code[ans[i][j]>>2]&2) b |= vertical(i,j);
			}
			++cnt;
			if(b) cnt = 0;
		}
	}
	
public:
	vector<int> create(int _H, int _W, vector<string> lights) {
		//prepare
		H = _H; W = _W;
		h_min = 1; h_max = H;
		w_min = 1; w_max = W;
		repp(i,0,H*W){
			tile[((lights[i][0]-'0')<<2)+(lights[i][1]-'a')].push_back(i);
		}
		color_num = 4;
		while(tile[color_num-1].size() == 0) --color_num;
		repp(i,0,NT) tile_count[i] = tile[i].size();
		repp(i,1,H+1) fill(ans[i]+1,ans[i]+W+1,-1);
		fill(ans[0],ans[0]+W+2,NT);
		fill(ans[H+1],ans[H+1]+W+2,NT);
		repp(i,1,H+1) ans[i][0] = ans[i][W+1] = NT;
		bestscore = H*W;
		
		//solve
		solveA();
		repp(i,0,NT) tile_count[i] = tile[i].size();
		repp(i,1,H+1) fill(ans[i]+1,ans[i]+W+1,-1);
		h_min = 1; h_max = H;
		w_min = 1; w_max = W;
		solveB();
		
		//output
		vector<int> ret(H*W,-1);
		repp(i,1,H+1) repp(j,1,W+1) if(~best[i][j]){
			auto &tmp = tile[best[i][j]];
			ret[i*W+j-1-W] = *(tmp.rbegin());
			tmp.pop_back();
		}
		int z = 0;
		repp(i,1,H+1) repp(j,1,W+1) if(!~best[i][j]){
			while(!tile[z].size()) ++z;
			ret[i*W+j-1-W] = *(tile[z].rbegin());
			tile[z].pop_back();
		}
		return ret;
	}
};

反省

　スコアの差は$7$位と$4k$、$1$位と$6k$ほどある。 TLEが3ケースで出ていたことで$1.5k$ほどスコアが下がったようだが、それでも上位とは離されている。
　初日に焼きなましは不要だと感じたのだが、実行時間が余っていたのだから山登りを焼きなましにすることを検討すべきであった。 ただ焼きなましを導入するにあたっての障壁が、遷移として適切なものを見つけることである。 自分はこれを考えるのが面倒というところで止まってしまったので論外である。 面倒であることと有効でないことは一致しないので、面倒だという理由で考えるのをやめてしまってはいけない。
　もう一つ自分がやるべきだったのは、理論値の計算である。 これをすれば上位の人が理論値に達していることにはっきり気付くことができたはずだ。 また目標を理論値に設定することができ、そのためには何が必要であるかを考えるきっかけにすることができただろう。 マラソンマッチは厳密解を出せるとは限らないのだが、絶対に出せないというわけでもないことは心に刻んでおきたい。

---

＜(古い記事) Topcoder Marathon Match 96

関連

(新しい記事)＞

＜(古い記事) Topcoder Marathon Match 96

カテゴリー「競プロ 参戦記録」

第4回 ドワンゴからの挑戦状 予選 (新しい記事)＞

＜(古い記事) Topcoder Marathon Match 96

全体

第4回 ドワンゴからの挑戦状 予選 (新しい記事)＞

自己紹介

プログラミングとか合成音声とか
詳しくはこちら
twitter
Follow @PItS_blog

プライバシーポリシー

個人情報利用についてはこちら

最終更新日：2023.03.05

お問い合わせ

このページに関するお問い合わせはこちら

競技プログラミングMENU

問題を解くまでの道のり

• AtCoder
• Topcoder

その他

• ライブラリ
• コンテスト実況(YouTube)
• 競プロに関するあれこれ
• 競プロ 参戦記録

全体MENU

• UST Generator
• ブログ
• 競技プログラミング

寄付モドキ

0冂から10000冂まで
詳しくはこちら

© 2017- PItS