SRM 295 DIV1 Hard TribbloTrouble

SRM 行列

問題 Editorial

問題

略

解答

状態を圧縮する。
スタート・Wの場所のそれぞれ4方向分の状態と止まった状態を考えればいい。
その関係式を行列累乗でやる。
ガウスの消去法で解いても出来ると思う。http://d.hatena.ne.jp/anta1/20130217/1361087344のように

コメント

色々ややこしい書き方をしてしまった。
自分はWを入ってきた時と出ていく時それぞれで状態を作っているが、入ってきた時の状態だけでいい。
変な書き方をしたせいでさらに複雑になってさらに変なことになっている。
そして提出に1.5時間以上かかってしまった。
意外と本番で解いている人も多い。
Practice Roomの他の人や本番で解いた人のコードを見ると、全然シンプル。もっとシンプルに書きたい

コード

#include <string>
#include <vector>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;
typedef vector<string> vs;

typedef double Num;
struct Matrix {
	static const int MatN = 86;
	Num a[2][MatN][MatN];
	Num (*v)[MatN], (*w)[MatN];
	Matrix(): v(a[0]), w(a[1]) { mset(a, 0); }
	inline Num& at(int i, int j) { return v[i][j]; }
	inline const Num& at(int i, int j) const { return v[i][j]; }
	static Matrix identity(const Matrix&) {
		Matrix A;
		rep(i, MatN) A.at(i, i) = 1;
		return A;
	}
	Matrix& operator*=(const Matrix& B) {
		rep(i, MatN) rep(j, MatN) {
			Num x = 0;
			rep(k, MatN)
				x += at(i, k) * B.at(k, j);
			w[i][j] = x;
		}
		swap(v, w);
		return *this;
	}
};

const int dy[4] = {0, 1, 0, -1}, dx[4] = {1, 0, -1, 0};
int dfsmemo[4][111][111][2];

struct TribbloTrouble {
	int h, w;
	vs code;
	int index[4][111][111];
	static const int NeverTerminate = 0, Terminate = 1, Starts = 2,
			Wherevers = 6, WhereverGoes = 6 + 40;
	int dfs(int d, int i, int j, bool mirrored) {
		static const int Check = -2;
		int r;
		if(dfsmemo[d][1+i][1+j][mirrored] != -1) {
			if(dfsmemo[d][1+i][1+j][mirrored] == Check) r = NeverTerminate;
			else r = dfsmemo[d][1+i][1+j][mirrored];
		}else {
			static const int mirror1[4] = {3, 2, 1, 0}, mirror2[4] = {1, 0, 3, 2};
			dfsmemo[d][i][j][mirrored] = Check;
			if(i < 0 || i >= h*2 || j < 0 || j >= w*2) r = NeverTerminate;
			else if(index[d][i][j] != -1) r = index[d][i][j];
			else if(!mirrored && i%2==0 && j%2==0 && code[i/2][j/2] == '/') r = dfs(mirror1[d], i, j, true);
			else if(!mirrored && i%2==0 && j%2==0 && code[i/2][j/2] == '\\') r = dfs(mirror2[d], i, j, true);
			else r = dfs(d, i+dy[d], j+dx[d], false);
		}
		return dfsmemo[d][1+i][1+j][mirrored] = r;
	}
	double terminates(vector <string> code_) {
		mset(index, -1);
		code = code_;
		code.insert(code.begin(), string(code[0].size(), '.'));
		code.insert(code.end(), string(code[0].size(), '.'));
		rep(i, code.size()) code[i] = "." + code[i] + ".";
		h = code.size(), w = code[0].size();
		int wCount = 0;
		Matrix A;
		rep(i, h) rep(j, w) {
			int y = i * 2, x = j * 2;
			if(code[i][j] == 'S') {
				rep(d, 4) index[d][y][x] = NeverTerminate;
				rep(d, 4) {
					int yy = y + dy[d], xx = x + dx[d];
					if(yy<0||yy>=h*2||xx<0||xx>=w*2) continue;
					index[d][yy][xx] = Starts + d;
				}
			} else if(code[i][j] == 'W') {
				rep(d, 4) {
					index[d][y][x] = Wherevers + wCount * 4 + d;
					int yy = y + dy[d], xx = x + dx[d];
					if(yy<0||yy>=h*2||xx<0||xx>=w*2) continue;
					index[d][yy][xx] = WhereverGoes + wCount * 4 + d;
				}
				wCount ++;
			}else if(code[i][j] == 'T') {
				rep(d, 4) index[d][y][x] = Terminate;
			}
		}
		mset(dfsmemo, -1);
		rep(d, 4) rep(i, h*2) rep(j, w*2) {
			int idx = index[d][i][j];
			if((Starts <= idx && idx < Starts + 4) || (WhereverGoes <= idx && idx < WhereverGoes + 40)) {
				int memoval = dfsmemo[d][i+dy[d]+1][j+dx[d]+1][0];
				A.at(idx, memoval != -1 ? memoval : dfs(d, i + dy[d], j + dx[d], false)) += 1;
			}
		}
		rep(i, wCount) rep(d, 4) {
			rer(f, -1, 1) if(f)
				A.at(Wherevers + i * 4 + d, WhereverGoes + i * 4 + (d+f+4)%4) += .5;
		}
		A.at(Terminate, Terminate) ++; A.at(NeverTerminate, NeverTerminate) ++;
		rep(i, 50) A *= A;
		double r = 0;
		rep(d, 4) r += A.at(Starts + d, Terminate) / 4;
		return r;
	}
};