HackerRank University CodeSprint3 : F. March of the King

間に合うか危なかったけど何とか間に合った。
https://www.hackerrank.com/contests/university-codesprint-3/challenges/march-of-the-king

問題

8*8のグリッドにアルファベットが１文字ずつ書かれている。
ここである文字列が与えられる。
任意のマスから始め、上下左右斜めを含めた隣接8マスを重複なく文字列の文字数と同じマスだけたどったとき、通過したマスの文字を順に並べたとき入力の文字列と一致するのは何通りか。

解法

9文字までなら愚直にDFS等で総当たりで間に合う。
10文字11文字は半分全列挙をする。

以下11文字の例を示す。
中心である6文字目のマスを定めたとき、前の５文字と後ろの５文字の移動順を列挙しよう。
その時、両移動経路が同じマスを含まないようなものの組み合わせを数え上げる。
現在位置から５回以内の移動で到達できるマスは高々121個なので、128bitで通るマスを覚えておけば、同じマスを含むかどうか高速に判定できる。

int K;
string A;
string S[8];
int vis[8][8];
ll ret;
vector<vector<pair<int,int>>> cand[6];
vector<pair<ll,ll>> mask[6];
vector<bitset<16000>> c2[6];
bitset<16000> bs;


void dfs(int y,int x,int step) {
	if(vis[y][x]) return;
	if(S[y][x]!=A[step-1]) return;
	if(step==K) {
		ret++;
	}
	else {
		vis[y][x]=1;
		for(int cy=max(0,y-1);cy<=min(7,y+1);cy++) {
			for(int cx=max(0,x-1);cx<=min(7,x+1);cx++) {
				dfs(cy,cx,step+1);
			}
		}
		vis[y][x]=0;
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>K>>A;
	FOR(y,8) cin>>S[y];
	if(K<=9) {
		FOR(y,8) FOR(x,8) dfs(y,x,1);
	}
	else {
		cand[0].push_back(vector<pair<int,int>>({{0,0}}));
		int id=(0+5)*11+(0+5);
		mask[0].push_back({0,0});
		for(i=1;i<=5;i++) {
			FOR(j,cand[i-1].size()) {
				auto& c=cand[i-1][j];
				ll ma=mask[i-1][j].first;
				ll mb=mask[i-1][j].second;
				for(y=c.back().first-1;y<=c.back().first+1;y++) {
					for(x=c.back().second-1;x<=c.back().second+1;x++) {
						if(y==0 && x==0) continue;
						int id=(y+5)*11+(x+5);
						ll a=(id<60)?(1LL<<id):0;
						ll b=(id>=60)?(1LL<<(id-60)):0;
						
						if((ma&a)==0 && (mb&b)==0) {
							cand[i].push_back(c);
							cand[i].back().push_back({y,x});
							mask[i].push_back({ ma|a, mb|b});
						}
					}
				}
			}
			c2[i].resize(cand[i].size());
		}
		for(i=4;i<=5;i++) {
			FOR(x,cand[i].size()) {
				FOR(j,cand[5].size()) {
					if(mask[i][x].first&mask[5][j].first) continue;
					if(mask[i][x].second&mask[5][j].second) continue;
					c2[i][x][j]=1;
				}
			}
		}
		
		FOR(y,8) FOR(x,8) {
			FOR(j,cand[5].size()) {
				auto &c=cand[5][j];
				FOR(k,c.size()) {
					int cy=y+c[k].first;
					int cx=x+c[k].second;
					if(cy<0 || cy>=8 || cx<0 || cx>=8) break;
					if(S[cy][cx] != A[(K-1)/2+k]) break;
				}
				bs[j]=(k==c.size());
			}
			FOR(j,cand[(K-1)/2].size()) {
				auto &c=cand[(K-1)/2][j];
				FOR(k,c.size()) {
					int cy=y+c[k].first;
					int cx=x+c[k].second;
					if(cy<0 || cy>=8 || cx<0 || cx>=8) break;
					if(S[cy][cx] != A[(K-1)/2-k]) break;
				}
				if(k==c.size()) {
					bitset<16000> b=bs&c2[(K-1)/2][j];
					ret+=b.count();
				}
			}
			
		}
	}
	cout<<ret<<endl;
	
}

まとめ

11文字はTLEすると思ったんだけど通って意外。