HAL2011

c++

/**
 * @file
 * @brief 参加者が解答を記述するファイル。
 */
#include "HPCIncludes.hpp"
//#include "cstdio"

//----------------------------------------------------------
using namespace hpc; // 名前空間が不必要な場合はこのように記述。

//----------------------------------------------------------
/**
 * @brief ステージ開始時に呼ばれる関数。
 * @return スタート地点を返してください。ここで返した座標から移動開始になります。
 * @param aField ステージの舞台となるフィールド。
 *               フィールドの高さや幅、フィールドを構成する各マスへアクセスできます。
 */

/*
 方針の概要
 
 「つなぐ」
 有用なかけ算マスを最短経路でつないでいき、不要なかけ算マスを排除
 マイナスのかけ算がある場合は先頭に持ってくる(正負両方の足し算マスを最大限に利用するため)
 
 「のばす」
 経路の始点を延長していく
 先頭部分の足し算が大きい程得点はのびる
 
 「ふくらます」
 "|" の部分を "コ" のように膨らましていく
 */


//マクロは真っ黒
#define movex(x,i) ((x+dx[i]+width-1)%width+1)
#define movey(y,i) ((y+dy[i]+height-1)%height+1)
#define backx(x,i) ((x-dx[i]+width-1)%width+1)
#define backy(y,i) ((y-dy[i]+height-1)%height+1)
#define smovex(x,i,j) ((x+subx[i][j]+width-1)%width+1)
#define smovey(y,i,j) ((y+suby[i][j]+height-1)%height+1)
#define sum(x,y,k) ((fnum[smovex(x,k,0)][smovey(y,k,0)]+fnum[smovex(x,k,1)][smovey(y,k,1)])*chugo)


//定数たち
const Action act_num[5] = {Action_MoveLeft, Action_MoveRight, Action_MoveDown, Action_MoveUp, Action_Stop};
const int dx[4] = {-1,1,0,0}, dy[4] = {0,0,-1,1}; //移動用
const int son = -15; // 「のばす」で -15以下の損を避ける
const int tousi = -20; // 「ふくらます」で 合計-20までの損なら投資だと思って許容する
const int asicut = 100; // -99% ~ 99% のマスを排除
const int rann = 196; // 乱数部分の試行回数

//「ふくらます」用のオートマトン
const int subx[8][2] = {{0,-1},{0,-1},{0,1},{0,1},{-1,-1},{1,1},{-1,-1},{1,1}};
const int suby[8][2] = {{-1,-1},{1,1},{-1,-1},{1,1},{0,-1},{0,-1},{0,1},{0,1}};
const int subi[8][3] = {{5,0,6},{7,1,4},{4,2,7},{6,3,5},{1,4,2},{3,5,0},{0,6,3},{2,7,1}};


//ヒープ用の構造体
struct data{ int w, x, y, i;};

//グローバル変数たち
char rec[1050]; //答えとする経路を記録
bool yet[100][100], qyet[100][100]; // 通ったか否か
int fnum[100][100]; // フィールドの数字
bool fkind[100][100]; // フィールドの種類
int mulx[100], muly[100]; // かけ算マスの位置
int nows, kosu, maxr, maxs, ti; // グローバルである必要が不明なものも含め()変数
int qx[5000], qy[5000], qpre[5000], qs, qt, pre[100][100]; // 自前くぅえうえ
int next[100][100]; // 経路を記録
int hugo; // 経路上での符号

//コピー用
bool cyet[100][100]; // 通ったか否か
int chugo; // 経路上での符号
int cnext[rann][100][100]; // 経路を記録
int motx, moty; // x,y
int anstx, ansty; // 答えの初期位置

//最大ヒープ
//構造体ごとswapするのは嫌だったので、ヒープのノードにはindexを記録している
//一ヶ所でしか使っていないこともあり、機能的にはかなり適当感が漂っているw
const int n12 = 1<<12;
int hi, node[n12];
data heap[n12];

void push(){
	int i = hi++, ni, ai, bi;
	while(i > 1){
		ni = i >> 1;
		ai = node[i]; bi = node[ni];
		if(heap[ai].w > heap[bi].w){
			node[i] = bi;
			node[ni] = ai;
		} else break;
		i = ni;
	}
}

void pop(){
	int i = --hi, ai, ni;
	ai = node[1]; node[1] = node[i]; node[i] = ai;
	heap[node[i]].w = -1000;
	while((i<<1)+1 <= hi){
		ni = i << 1;
		ai = node[i];
		if(heap[node[ni]].w < heap[node[ni+1]].w) ni++;
		if(heap[ai].w < heap[node[ni]].w){
			node[i] = node[ni];
			node[ni] = ai;
		} else break;
		i = ni;
	}
}
//



Pos Answer::Init( const Field& aField )
{
    // フィールドの幅を取得
    int width = aField.width();
    // フィールドの高さを取得
    int height = aField.height();
	
	//ここからは my space
	Random rnd; 
	Cell acell;
	int ri, i, j, k, x, y, allcell, nx, ny, stx, sty, x0, y0, x1, y1;
	int muli = 0, mulm = 0, mxm = -1000, mxmi;
	int ki, rnsu;
	data d;
	maxs = 0; maxr = 0;
	allcell = width * height;
	
	
	//フィールドを読み込む
	for(i = 0; i <= width+1; i++){
		for(j = 0; j <= height+1; j++){
			yet[i][j] = false;
			next[i][j] = -1;
		}
	}
	for(i = 1; i <= width; i++){
		for(j = 1; j <= height; j++){
			
			acell = aField.cell(i-1,j-1);
			
			fnum[i][j] = acell.num;
			if(acell.kind == Cell::Kind_Add){ //足し算マス
				yet[i][j] = true;
				fkind[i][j] = true;
			} else { // かけ算マス
				fkind[i][j] = false;
				if(fnum[i][j] >= asicut || fnum[i][j] <= -asicut){ // 有用なかけ算マス
					yet[i][j] = true;
					mulx[muli] = i;
					muly[muli++] = j;
					if(fnum[i][j] < 0){
						mulm++;
						if(mxm < fnum[i][j]){ mxm = fnum[i][j]; mxmi = muli-1;}
					}
				}
			}
		}
	}
	hugo = -1; // 符号は「負」にしておいているらしい
	
	if(muli != 0){//有用なかけ算マスがあるとき
		
		if(!mulm){
			//マイナスのかけ算マスがないとき
			mxmi = rnd.randMinMax(0,muli-1);
			hugo = 1;
		}
		
		//最初に通るかけ算マス(マイナスの中で最大のもの)から、近い順にBFSでつないでいく
		nx = mulx[mxmi]; ny = muly[mxmi];
		qx[0] = nx; qy[0] = ny;
		next[nx][ny] = -1;
		for(k = 0; k < muli; k++){
			//通過判定初期化
			for(i = 1; i <= width; i++){
				for(j = 1; j <= height; j++){
					qyet[i][j] = yet[i][j];
				}
			}
			
			qs = 0; qt = 1;
			qpre[0] = -1;
			
			//BFS本体
			while(qs < qt){
				nx = qx[qs]; ny = qy[qs];
				
				if(qyet[nx][ny]){
					qyet[nx][ny] = false;
					pre[nx][ny] = qpre[qs];
					
					if(!fkind[nx][ny] && qs != 0) break;
					
					for(i = 0; i < 4; i++){
						qx[qt] = movex(nx,i);
						qy[qt] = movey(ny,i);
						qpre[qt++] = i;
					}
				}
				
				qs++;
			}
			
			//queueが空なら終わり
			if(qs == qt) break;
			if(fnum[nx][ny] < 0) hugo = -hugo;
			
			//道筋を記録
			next[nx][ny] = -1;
			qx[0] = nx; qy[0] = ny;
			while(pre[nx][ny] != -1){
				i = pre[nx][ny];
				next[backx(nx,i)][backy(ny,i)] = i;
				nx = backx(nx,i); ny = backy(ny,i);
				yet[nx][ny] = false;
			}
		}
		
		yet[qx[0]][qy[0]] = false;
		x = mulx[mxmi]; y = muly[mxmi];
		
	} else { //有用なかけ算マスがないとき
		do{ // ランダムで暫定初期位置を選ぶ
			x = rnd.randMinMax(1,width);
			y = rnd.randMinMax(1,height);
		}while(!fkind[x][y]);
		next[x][y] = -1;
		yet[x][y] = false;
	}
	
	
	//ここから乱数導入で改善
	motx = x; moty = y;
	
	//ヒープ初期化
	hi = 1;
	for(i = 1; i < n12; i++) node[i] = i;
	
	for(int rani = 0; rani < rann; rani++){
		//いろいろコピー
		for(i = 1; i <= width; i++){
			for(j = 1; j <= height; j++){
				cnext[rani][i][j] = next[i][j];
				cyet[i][j] = yet[i][j];
			}
		}
		chugo = hugo;
		x = motx; y = moty;
		
		
		//のばす
		while(1){
			k = son;
			for(i = 0; i < 4; i++){
				nx = backx(x,i); ny = backy(y,i);
				if(cyet[nx][ny] && fnum[nx][ny]*chugo > k*rnd.randMinMax(0,90)/90){
					k = fnum[nx][ny]*chugo;
					ki = i;
				}
			}
			if(k == son) break;
			
			x = backx(x,ki); y = backy(y,ki);
			cnext[rani][x][y] = ki;
			cyet[x][y] = false;
		}
		stx = x; sty = y;
		
		
		
		//ふくらます
		//各かけ算マス間の経路について、先頭から順にふくらます
		rnsu = rnd.randMinMax(5,20);
		while(1){
			//経路上の辺をヒープに突っ込む
			do{
				i = cnext[rani][x][y];
				if(i == -1) break;
				nx = movex(x,i); ny = movey(y,i);
				
				k = i<<1; heap[node[hi]] = (data){sum(x,y,k)+rnd.randMinMax(0,rnsu),x,y,k}; push();
				k++; heap[node[hi]] = (data){sum(x,y,k)+rnd.randMinMax(0,rnsu),x,y,k}; push();
				x = nx; y = ny;
			}while(fkind[x][y]);
			
			//ふくらます本体
			while(hi > 1){
				d = heap[node[1]]; pop();
				x0 = smovex(d.x,d.i,0); y0 = smovey(d.y,d.i,0);
				x1 = smovex(d.x,d.i,1); y1 = smovey(d.y,d.i,1);
				
				if(cyet[x0][y0] && cyet[x1][y1] && (fkind[x0][y0] || fnum[x0][y0] > 0) && (fkind[x1][y1] || fnum[x1][y1] > 0) && d.w > tousi){
					cyet[x0][y0] = false;
					cyet[x1][y1] = false;
					cnext[rani][d.x][d.y] = subi[d.i][0] >> 1;
					cnext[rani][x0][y0] = subi[d.i][1] >> 1;
					cnext[rani][x1][y1] = subi[d.i][2] >> 1;
					
					heap[node[hi]] = (data){sum(d.x,d.y,subi[d.i][0])+rnd.randMinMax(0,rnsu),d.x,d.y,subi[d.i][0]}; push();
					heap[node[hi]] = (data){sum(x0,y0,subi[d.i][1])+rnd.randMinMax(0,rnsu),x0,y0,subi[d.i][1]}; push();
					heap[node[hi]] = (data){sum(x1,y1,subi[d.i][2])+rnd.randMinMax(0,rnsu),x1,y1,subi[d.i][2]}; push();
				}
			}
			
			if(fnum[x][y] < 0) chugo = -chugo;
			if(i == -1) break;
		}
		
		
		//スコア計算
		x = stx; y = sty; nows = 0; kosu = 0;
		while(1){
			if(fkind[x][y]){
				nows += fnum[x][y];
			} else {
				nows = nows*fnum[x][y]/100;
			}
			kosu++;
			i = cnext[rani][x][y];
			if(i == -1) break;
			x = movex(x,i);
			y = movey(y,i);
		}
		
		//スコアが良ければ更新
		if(maxs < nows*kosu/allcell){
			maxs = nows*kosu/allcell;
			anstx = stx; ansty = sty;
			maxr = rani;
		}
	}
	//ここまで乱数
	
	
	//recに変換
	ri = 0;
	x = anstx; y = ansty;
	while(1){
		i = cnext[maxr][x][y];
		if(i == -1) break;
		rec[ri++] = i;
		x = movex(x,i);
		y = movey(y,i);
	}
	rec[ri] = 4;
	
	
	ti = 0;
	
	//my space ここまで
	
    // スタート地点
	
	//stat++;
	Pos start( anstx-1, ansty-1 );
    return start;
}

//----------------------------------------------------------
/**
 * @brief 毎ターン呼ばれる関数。
 * @return このターンで行う行動を返してください。
 *         行動は「移動」と「終了宣言」ができます。
 *         行動については HPCAction.hppを参照してください。
 * @param aStage 現在のターンでのステージの状態。
 *               フィールドの情報や各々のマスへアクセスできるFieldオブジェクトや、
 *               現在の座標や現在のスコアへアクセスできるPlayerオブジェクトへアクセスできます。
 */
Action Answer::Next( const Stage& aStage )
{	
	return act_num[rec[ti++]]; // recに記録したものを吐き出すだけ
}

//----------------------------------------------------------
// EOF