Codeforces #331 Div2 E. Wilbur and Strings

本番時間切れ。
http://codeforces.com/contest/596/problem/E

問題

N行M列のセルからなる、各セル0～9の数字が埋まったボードが与えられる。
ここで以下の動作を考える。

任意の位置にコマを置いてゲームを始める。
コマの位置にあるセルの数値に対して、相対的にX行Y列ずれた位置にコマを進める。
(ただしその位置にコマを進めるとボード外に出てしまう場合、コマは進めない)

プレイヤーは手元の文字列が空の状態から始め、コマを動かす(または動けずその位置にとどまる)度に、そのセルの数字を文字列に1回追加することができる(追加しなくてもよい)。

ここでQ個のクエリが与えられる。
各クエリは0-9で構成された文字列からなる。
プレイヤーが適切な行動をとることで、その文字列を作れるか判定せよ。

解法

各セルから遷移する先は1つである。
よってこのボードにおける遷移グラフは、常に最後は閉路に落ち込む。

閉路に含まれる文字列は好きなだけ使えるので、文字列のpostfixのうち閉路のある分は除いて、残りを閉路外のマスで賄うと考えるとよい。

そのためには、まず遷移グラフの閉路を求めよう。
次に遷移グラフの辺を逆にしたグラフを考える。

各クエリにおいては、入力文字列を反転し、各閉路において、閉路内で賄える(反転後の)prefixを除いた文字列に対し、構築可能か逆順の遷移グラフでDFSするとよい。
閉路以外のセルはN*M個なので、DFSの処理オーダーは(N*M*Q)である。

int H,W,Q;
string S,T;
int DY[10],DX[10];

int nex[202*202];
int inloop[202*202];
int vis[202*202];
int mask[202*202];
vector<int> st;
vector<int> E[202*202];
int first[10];

int dfs(int cur,int first) {
	vis[cur]=first;
	if(vis[nex[cur]]==first) {
		st.push_back(nex[cur]);
		inloop[cur]=nex[cur];
		mask[inloop[cur]] |= 1<<S[cur];
		if(inloop[cur]==cur) return -1;
		return inloop[cur];
	}
	else if(vis[nex[cur]]>=0) {
		return -1;
	}
	else {
		inloop[cur]=dfs(nex[cur],first);
		mask[inloop[cur]] |= 1<<S[cur];
		if(inloop[cur]==-1 || inloop[cur]==cur) return -1;
		return inloop[cur];
	}
	
}

bool dfs2(int cur,int pos) {
	if(S[cur]==T[pos]) pos++;
	if(pos>=T.size()) return true;
	
	FORR(r,E[cur]) if(dfs2(r,pos)) return true;
	return false;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>Q;
	FOR(i,H) cin>>s, S+=s;
	FORR(r,S) r-='0';
	FOR(i,10) cin>>DY[i]>>DX[i];
	
	FOR(y,H) FOR(x,W) {
		int nx=x+DX[S[y*W+x]];
		int ny=y+DY[S[y*W+x]];
		
		if(nx<0 || nx>=W || ny<0 || ny>=H) nx=x, ny=y;
		nex[y*W+x]=ny*W+nx;
	}
	H*=W;
	MINUS(vis);
	MINUS(inloop);
	FOR(i,H) if(vis[i]==-1) dfs(i,i);
	
	
	FOR(i,H) if(inloop[i]==-1) {
		x=nex[i];
		if(inloop[x]>=0) x=inloop[x];
		E[x].push_back(i);
	}
	
	while(Q--) {
		cin>>T;
		reverse(ALL(T));
		FOR(i,10) first[i]=T.size();
		FOR(i,T.size()) {
			T[i]-='0';
			first[T[i]]=min(first[T[i]],i);
		}
		FORR(r,st) {
			int mi=T.size();
			FOR(i,10) if((mask[r] & (1<<i))==0) mi=min(mi,first[i]);
			if(mi==T.size() || dfs2(r,mi)) {
				cout<<"YES"<<endl;
				goto out;
			}
		}
		cout<<"NO"<<endl;
		out:
		;
	}
}

まとめ

閉路検出苦手。ライブラリにするか、SCC使いまわすか…。