SuperCon2011ソース

送っていただいたので貼ります。

ほかのチームに比べてずいぶんあっさりしていると思いますが、ちゃんとしたアルゴリズムを思いつかなかった＆運に任せた結果ですのでご了承を。

#include "sc11.h"/* sc11.h は必ずincludeすること */
#include <string.h>
#include <time.h>
#include <limits.h>
#include <random.h>

#define HOLE -1

int move(int dest[][SIZE], int src[][SIZE], int direction);
int move_left(int dest[][SIZE], int src[][SIZE]);
int move_up(int dest[][SIZE], int src[][SIZE]);
int move_right(int dest[][SIZE], int src[][SIZE]);
int move_down(int dest[][SIZE], int src[][SIZE]);

double rate_up(int src[][SIZE]){
	int i, j;
	int *frame = sc11_waku[UP];
	int fall_sum = 0, score = 0;

	for(j = 0; j < SIZE; j++) {
		// 上からループ
#pragma cdir nodep
		for(i = 0; i < SIZE; i++, fall_sum++) {
			if(src[i][j] == WALL) break;
			if(frame[j] == src[i][j]) {
				// puts("up");
				score++;
			}
		}
	}
	if(fall_sum == 0) return 0;
	return (double)score / fall_sum;
}

double rate_right(int src[][SIZE]){
	int i, j;
	int *frame = sc11_waku[RIGHT];
	int fall_sum = 0, score = 0;

	for(i = 0; i < SIZE; i++) {
		// 右からループ
#pragma cdir nodep
		for(j = SIZE - 1; j >= 0; j--, fall_sum++) {
			if(src[i][j] == WALL) break;
			if(frame[i] == src[i][j]) {
				// puts("right");
				score++;
			}
		}
	}

	if(fall_sum == 0) return 0;
	return (double)score / fall_sum;
}

double rate_left(int src[][SIZE]){
	int i, j;
	int *frame = sc11_waku[LEFT];
	int fall_sum = 0, score = 0;

	for(i = 0; i < SIZE; i++) {
		// 左からループ
#pragma cdir nodep
		for(j = 0; j < SIZE; j++, fall_sum++) {
			if(src[i][j] == WALL) break;
			if(frame[i] == src[i][j]) {
				// puts("left");
				score++;
			}
		}
	}

	if(fall_sum == 0) return 0;
	return (double)score / fall_sum;
}


double rate_down(int src[][SIZE]) {
	int i, j;
	int *frame = sc11_waku[DOWN];
	int fall_sum = 0, score = 0;

	for(j = 0; j < SIZE; j++) {
		// 下からループ
#pragma cdir nodep
		for(i = SIZE - 1; i >= 0; i--, fall_sum++) {
			if(src[i][j] == WALL) break;
			if(frame[j] == src[i][j]) {
				// puts("down");
				score++;
			}
		}
	}

	if(fall_sum == 0) return 0;
	return (double)score / fall_sum;
}

double rate_move(int src[][SIZE], int direction){
	switch(direction){
		case UP:
			return rate_up(src);
		case RIGHT:
			return rate_right(src);
		case DOWN:
			return rate_down(src);
		case LEFT:
			return rate_left(src);
	}
}

int move(int dest[][SIZE], int src[][SIZE], int direction){
	switch(direction){
		case UP:
			return move_up(dest, src);
		case RIGHT:
			return move_right(dest, src);
		case DOWN:
			return move_down(dest, src);
		case LEFT:
			return move_left(dest, src);
	}
	return -1;
}

int move_up(int dest[][SIZE], int src[][SIZE]){
	int retval = 0, i, j;
	int bottom[SIZE];
	int *frame = sc11_waku[UP];

	/* bottomの初期化処理 */
	for(i=0; i<SIZE; i++){
		bottom[i] = (frame[i] == WALL ? 0 : HOLE);
	}

	/* destの初期化処理 */
	for(i=0; i<SIZE; i++){
		for(j=0; j<SIZE; j++){
			dest[i][j] = EMPTY;
		}
	}

	/* 遷移処理 */
	for(i=0; i<SIZE; i++){
#pragma cdir nodep
		for(j=0; j<SIZE; j++){
			if(src[i][j] == WALL){
				bottom[j] = i + 1;
				dest[i][j] = WALL;
			}
			else if(bottom[j] == HOLE){
				retval += (frame[j] == src[i][j] ? 1 : 0);
				dest[i][j] = EMPTY;
			}
			else if(src[i][j] != EMPTY){
				dest[bottom[j]][j] = src[i][j];
				bottom[j]++;
			}
		}
	}

	return retval;
}

int move_right(int dest[][SIZE], int src[][SIZE]){
	int retval = 0, i, j;
	int bottom[SIZE];
	int *frame = sc11_waku[RIGHT];

	/* bottomの初期化処理 */
	for(i=0; i<SIZE; i++){
		bottom[i] = (frame[i] == WALL ? SIZE-1 : HOLE);
	}

	/* destの初期化処理 */
	for(i=0; i<SIZE; i++){
		for(j=0; j<SIZE; j++){
			dest[i][j] = EMPTY;
		}
	}

	/* 遷移処理 */
	for(j=SIZE-1; j>=0; j--){
#pragma cdir nodep
		for(i=0; i<SIZE; i++){
			if(src[i][j] == WALL){
				bottom[i] = j - 1;
				dest[i][j] = WALL;
			}
			else if(bottom[i] == HOLE){
				retval += (frame[i] == src[i][j]);
				dest[i][j] = EMPTY;
			}
			else if(src[i][j] != EMPTY){
				dest[i][bottom[i]] = src[i][j];
				bottom[i]--;
			}
		}
	}

	return retval;
}

int move_down(int dest[][SIZE], int src[][SIZE]){
	int retval = 0, i, j;
	int bottom[SIZE];
	int *frame = sc11_waku[DOWN];

	/* bottomの初期化処理 */
	for(i=0; i<SIZE; i++){
		bottom[i] = (frame[i] == WALL ? SIZE-1 : HOLE);
	}
	/* destの初期化処理 */
	for(i=0; i<SIZE; i++){
		for(j=0; j<SIZE; j++){
			dest[i][j] = EMPTY;
		}
	}

	/* 遷移処理 */
	for(i=SIZE-1; i>=0; i--){
#pragma cdir nodep
		for(j=0; j<SIZE; j++){
			if(src[i][j] == WALL){
				bottom[j] = i - 1;
				dest[i][j] = WALL;
			}
			else if(bottom[j] == HOLE){
				retval += (frame[j] == src[i][j] ? 1 : 0);
				dest[i][j] = EMPTY;
			}
			else if(src[i][j] != EMPTY){
				dest[bottom[j]][j] = src[i][j];
				bottom[j]--;
			}
		}
	}

	return retval;
}

int move_left(int dest[][SIZE], int src[][SIZE]){
	int retval = 0, i, j;
	int bottom[SIZE];
	int *frame = sc11_waku[LEFT];

	/* bottomの初期化処理 */
	for(i=0; i<SIZE; i++){
		bottom[i] = (frame[i] == WALL ? 0 : HOLE);
	}
	/* destの初期化処理 */
	for(i=0; i<SIZE; i++){
		for(j=0; j<SIZE; j++){
			dest[i][j] = EMPTY;
		}
	}

	/* 遷移処理 */
	for(j=0; j<SIZE; j++){
#pragma cdir nodep
		for(i=0; i<SIZE; i++){
			if(src[i][j] == WALL){
				bottom[i] = j + 1;
				dest[i][j] = WALL;
			}
			else if(bottom[i] == HOLE){
				retval += (frame[i] == src[i][j]);
				dest[i][j] = EMPTY;
			}
			else if(src[i][j] != EMPTY){
				dest[i][bottom[i]] = src[i][j];
				bottom[i]++;
			}
		}
	}

	return retval;
}

void solve(){
	int turn, dir, best_score = -1, best_move, score;
	int s_length;
	int current_board[SIZE][SIZE], tmp_board[SIZE][SIZE];
	int current_solution[SOLUTION_LENGTH];
	double sum, r[SOLUTION_LENGTH], add, point[4], point_rate[4];
	float random_field[2048];
	franvi(random_field);

	if(sc11_timelimit == 5) {
		s_length = 950;
	} else if(sc11_timelimit == 10) {
		s_length = 2300;
	} else {
		s_length = 5500;
	}

	for(;;) {
		score = 0;
		memcpy(current_board, sc11_board, sizeof current_board);
		for(turn = 0; turn < s_length; turn++) {
			r[turn] = franv(random_field);
		}
		for(turn=0; turn<s_length; turn++){
			sum = 0;
			add = 0;
			best_move = -1;
			for(dir = 0; dir < 4; dir++) {
				sum += (point[dir] = rate_move(current_board, dir));
			}
			// this will crash when sum == 0
			if (sum == 0) {
				best_move = (int)(r[turn] * 4);
			} else {
				for(dir = 0; dir < 4; dir++) {
					point_rate[dir] = point[dir] / sum;
					if(add <= r[turn] && r[turn] < add + point_rate[dir]) {
						best_move = dir;
						break;
					}
					add += point_rate[dir];
				}
				if(best_move == -1) {
					best_move = (int)(rand() / (RAND_MAX + 1.0) * 4);
				}
			}

			current_solution[turn] = best_move;
			score += move(tmp_board, current_board, best_move);
			memcpy(current_board, tmp_board, sizeof current_board);
		}
		if(score > best_score) {
			best_score = score;
			for(turn = 0; turn < s_length; turn++) {
				sc11_solution[turn] = current_solution[turn];
			}
			sc11_output();
		}
	}
}

int main(int argc, char* argv[]){
	sc11_init(argc, argv); /* 最初にsc11_initを呼ぶこと */
	//sc11_save(sc11_board,"test_output"); /* 盤面出力関数 */
	solve(); /* 解答を作る */
	return 0;
}

ホームディレクトリまるごと送っていただいたので、写真もぺたぺた

傾けたときに落ちるボールは決まっている話
（上に傾けたときに落ちるボールの位置を赤で着色）

落ちるボールの論理和を取るのはおいしくないという話。
（これは上と左に傾けて、どちらでも落ちる場所）

探索を途中で打ち切っている理由
（WALL20%, 完全乱択で5500回傾けたときの盤面の様子）

僕が3Step-Greedyを諦めた理由
（1回の3Step探索で得点として見ることのできる範囲）

同5Step-Greedyのとき

SuperCon-erはカントリーマアムが大好きだという話