読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

ICPC2015 模擬国内予選 D問題 「アリスハウス」

ICPC

実装&デバッグが間に合わなかったシリーズpart1
本番中は私が実装してました。
なお効率の悪い書き方をしていたため半分も書けずタイムオーバー。

ゲーム理論が国内予選で出るとは思ってなかった。
問題内容としては後退解析をするだけの典型ともいえる(後退解析が典型かどうかはさておき)
後退解析はARC038のD「有向グラフと数」で経験したのでアルゴリズムを思いつくまでは時間がかからなかったです。
アルゴリズム自体はARCの方が難しいので後退解析を知っていれば解ける。(と思う)自分の場合は実装が苦手なのでそこで躓きました。
状態変数が4つあるので実装のバグを招きやすいのが一番きつかったです。

問題概要

説明難しいので公式の問題文見てもらえると助かります。

H行W列のマスがあり、各マスの間には壁があるとことないとこがある。
アリスは最初(R,C)にいる。
アリスのターンから始まり、各ターン交互に次の動作を行う。

  • アリスのターン
    • 上下左右に移動することができる。
    • マスの外に移動できたら脱出成功となりアリスの勝ちとなる。
  • ボブのターン
    • なにもしない、または全ての壁を反転させることができる。
    • 反転とは、壁の無い部分に壁を出現させ、壁のある部分を壁の無い状態にすることである。

アリスが脱出できるなら勝ち、そうで無ければボブの勝ちとなる。

解説

まず勝利条件をまとめると、

  • アリス
    • 脱出できれば勝ち。
  • ボブ
    • アリスが脱出できなければ勝ち。
    • 具体的には、アリスの四方を壁で囲む。orアリスが脱出できないように壁を操作し無限に移動を繰り返させる。

という風になります。

メモ化バックトラックで解きたくなりますが、

  • 状態遷移のループがある。
  • 終了条件が2種類(脱出or四方囲み)

の二つ(主に一つ目)があるので難しい模様です。
メモ化バックトラックで本番通ったコードも終了後に作られたテストケースで落ちたという報告もあるみたいなので最適解法ではなさそうです。

そこで後退解析の出番です。
イメージとしては状態が確定したところから広げていくイメージ
1. まず入力で与えられた初期状態から既に勝敗が決まっている状態があるはずなので、その状態を上書きし、キューに入れます。
[この問題の場合]
アリスのターンかつ上下左右壁の無い方向のどこかへ進めば脱出できる状態→アリスの勝ち
アリスのターンかつ上下左右壁に囲まれた状態→ボブの勝ち

2. キューから取りだした状態から、その状態に遷移することのできる状態を列挙し、状態を更新します。

  • 自分のターンかつ自分が勝利できる状態が遷移後に一つでもあるならばそれを選べば良いので勝利が確定。
  • 遷移後の状態が全て相手の勝利できる状態ならば勝つことができないので負けが確定

これを元に状態を確定させていきます。確定した場合はその状態をキューに入れます。後者の場合はカウントを増やすのが良いでしょう。
[この問題の場合]

  • その状態に遷移することのできる状態
    • アリスのターン ← 座標そのままかつ壁がそのままor壁が反転した状態
    • ボブのターン  ← 壁がそのままかつ座標が上下左右の状態

3. キューの中身が空になったら探索終了。
このときのスタート地点の状態が答えです。
状態が未定のままなら二人が最善を尽くしたとき無限にゲームが終わらないということを指します。この問題の場合は未定でもアリスの負けとなります。

実装ミスをしやすいポイント

実装&デバッグしてて大事だなと思ったところをつらつらと

  • 状態変数が4つ(行番号、列番号、手番、壁)。壁のパターンは2種類あるので状態変数に加える必要があります。

4次元配列で表現するときにはできるだけfor文で配列アクセス、手動で状態変数を指定するときにはマクロを使ってわかりやすく

  • 入力が複雑

入力ルーチンと初期化ルーチンをしっかり分けた方がいいと感じた。

  • 番兵が使えそうなところはしっかり使う

コードが長くなるとそれだけ実装時間もミスも増えます。

  • 同じ状態をキューに二度入れない

初期化ルーチンで起こりやすい事故です。カウントする部分で崩れてきます。

ソースコード

これでも頑張って短く押さえた方です

#include<fstream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>

using namespace std;
#define NONE -1
#define ALICE 1
#define BOB 0
#define ON 1
#define OFF 0
#define UP 1
#define LEFT 0
#define DOWN 3
#define RIGHT 2

const int dir[] = { 0, -1, 0, 1, 0 };
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VVVI> VVVVI;
struct data{
	int x, y, turn, wall;
	data(int _x, int _y, int _turn, int _wall){
		x = _x; y = _y; turn = _turn; wall = _wall;
	}
};
int main(){
	ifstream cin("D.in");
	ofstream cout("D.out");
	while (1){
		int H, W, R, C;
		cin >> H >> W >> R >> C;
		if (H == 0 && W == 0 && R == 0 && C == 0)break;
		//[x][y][turn][wall]
		VVVVI state(H + 2, VVVI(W + 2, VVI(2, VI(2, NONE))));
		VVVVI cnt(H + 2, VVVI(W + 2, VVI(2, VI(2, 0))));
		for (int i = 0; i < H + 2; i++)for (int t = 0; t<2; t++)for (int w = 0; w < 2; w++)state[i][0][t][w] = state[i][W + 1][t][w] = ALICE;
		for (int i = 0; i < W + 2; i++)for (int t = 0; t<2; t++)for (int w = 0; w < 2; w++)state[0][i][t][w] = state[H + 1][i][t][w] = ALICE;
		//[x][y][wall][dir]
		VVVVI wall(H + 1, VVVI(W + 1, VVI(2, VI(4, ON))));
		VVI input_w(H + 1, VI(W + 2));
		VVI input_h(H + 2, VI(W + 1));
		for (int i = 1; i <= H; i++){
			for (int j = 1; j <= W; j++)cin >> input_h[i][j];
			for (int j = 1; j <= W + 1; j++)cin >> input_w[i][j];
		}
		for (int j = 1; j <= W; j++)cin >> input_h[H + 1][j];

		for (int i = 1; i <= H; i++)
			for (int j = 1; j <= W; j++)
				for (int w = 0; w<2; w++){
					wall[i][j][w][UP] = input_h[i][j] ^ w;
					wall[i][j][w][LEFT] = input_w[i][j] ^ w;
					wall[i][j][w][DOWN] = input_h[i + 1][j] ^ w;
					wall[i][j][w][RIGHT] = input_w[i][j + 1] ^ w;
				}

		queue<data> que;
		for (int i = 1; i < H + 1; i++)for (int w = 0; w < 2; w++){
			if (wall[i][1][w][LEFT] == OFF)if (state[i][1][ALICE][w] == NONE){ state[i][1][ALICE][w] = ALICE; que.push(data(i, 1, ALICE, w)); }
			if (wall[i][W][w][RIGHT] == OFF)if (state[i][W][ALICE][w] == NONE){ state[i][W][ALICE][w] = ALICE; que.push(data(i, W, ALICE, w)); }
		}
		for (int i = 1; i < W + 1; i++)for (int w = 0; w < 2; w++){
			if (wall[1][i][w][UP] == OFF)if (state[1][i][ALICE][w] == NONE){ state[1][i][ALICE][w] = ALICE; que.push(data(1, i, ALICE, w)); }
			if (wall[H][i][w][DOWN] == OFF)if (state[H][i][ALICE][w] == NONE){ state[H][i][ALICE][w] = ALICE; que.push(data(H, i, ALICE, w)); }
		}
		for (int i = 1; i <= H; i++)for (int j = 1; j <= W; j++)for (int w = 0; w < 2; w++)if (state[i][j][ALICE][w] == NONE){
			for (int d = 0; d < 4; d++){
				cnt[i][j][ALICE][w] += wall[i][j][w][d];
			}
			if (cnt[i][j][ALICE][w] == 4){ state[i][j][ALICE][w] = BOB; que.push(data(i, j, ALICE, w)); }
		}

		while (que.empty() == false){
			auto v = que.front(); que.pop();
			auto now = state[v.x][v.y][v.turn][v.wall];
			if (v.turn == ALICE&&now == BOB){
				int xx = v.x, yy = v.y, tt = 1 - v.turn;
				for (int ww = 0; ww < 2; ww++)
					if (state[xx][yy][tt][ww] == NONE){
						state[xx][yy][tt][ww] = now;
						que.push(data(xx, yy, tt, ww));
					}
			}
			else
			if (v.turn == BOB&&now == ALICE){
				int tt = 1 - v.turn, ww = v.wall;
				for (int d = 0; d < 4; d++){
					int xx = v.x + dir[d], yy = v.y + dir[d + 1];
					if (state[xx][yy][tt][ww] == NONE&&wall[v.x][v.y][ww][d] == OFF){
						state[xx][yy][tt][ww] = now;
						que.push(data(xx, yy, tt, ww));
					}
				}
			}
			else
			if (v.turn == ALICE&&now == ALICE){
				int xx = v.x, yy = v.y, tt = 1 - v.turn;
				for (int ww = 0; ww < 2; ww++)
					if (state[xx][yy][tt][ww] == NONE){
						cnt[xx][yy][tt][ww]++;
						if (cnt[xx][yy][tt][ww] == 2){
							state[xx][yy][tt][ww] = now;
							que.push(data(xx, yy, tt, ww));
						}
					}
			}
			else
			if (v.turn == BOB&&now == BOB){
				int tt = 1 - v.turn, ww = v.wall;
				for (int d = 0; d < 4; d++){
					int xx = v.x + dir[d], yy = v.y + dir[d + 1];
					if (state[xx][yy][tt][ww] == NONE&&wall[v.x][v.y][ww][d] == OFF){
						cnt[xx][yy][tt][ww]++;
						if (cnt[xx][yy][tt][ww] == 4){
							state[xx][yy][tt][ww] = now;
							que.push(data(xx, yy, tt, ww));
						}
					}
				}
			}
		}
		if (state[R][C][ALICE][OFF] == ALICE)
			cout << "Yes" << endl;
		else cout << "No" << endl;

	}
	cin.close();
	cout.close();
	return 0;
}