Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-11-15SRM523 Div1(Practice)

SRM523 Div1 900 AlphabetPaths

| 02:29 | SRM523 Div1 900 AlphabetPaths - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM523 Div1 900 AlphabetPaths - SRM diary(Sigmar) SRM523 Div1 900 AlphabetPaths - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

パスの中間地点でパスを2つに分割すると、長さ11のパスの探索問題にオーダーが落ちる

中間地点をイテレーションし、長さ11のパスを全探索すれば解が算出できる

計算量は21^2*3^10*log(3^10)=4億くらい?実際にはある程度枝刈りが入るためこれよりは大分小さいと思う

計算量が厳しいため無駄な計算をしないように注意が必要

最初サイズ200万の配列を21^2回memsetしていたら余裕でTLEしてしまった。memsetは安易にしないほうがいいですね。。


ソースコード

これで最悪1.5秒くらいです

int cnt[1<<21];
vector <int> vis;
const string letter="ABCDEFZHIKLMNOPQRSTVX";
int letterid[30];

class AlphabetPaths {
public:
	int w, h;
	vector <string> maze;

	void dfs(int r, int c, int mask, int rem) {
		if(rem==0) {
			vis.push_back(mask);
			cnt[mask]++;
			return;
		}

		int dr[4]={1,-1,0,0}, dc[4]={0,0,1,-1};
		for(int i=0; i<4; i++) {
			int nr=r+dr[i], nc=c+dc[i];
			if(nr<0 || nr>=h || nc<0 || nc>=w) continue;
			if(maze[nr][nc]=='.') continue;
			if(mask&(1<<letterid[maze[nr][nc]-'A'])) continue;
			int nmask=(mask|(1<<letterid[maze[nr][nc]-'A']));
			dfs(nr, nc, nmask, rem-1);
		}
	}

	long long count(vector <string> letterMaze) {
		long long res=0;
		maze=letterMaze;
		h=maze.size();
		w=maze[0].size();
		const int allmask=(1<<21)-1;
		for(int i=0; i<21; i++) letterid[letter[i]-'A']=i;
		memset(cnt, 0, sizeof(cnt));

		for(int i=0; i<h; i++) {
			for(int j=0; j<w; j++) {
				if(maze[i][j]=='.') continue;
				vis.clear();
				int initmask=(1<<letterid[maze[i][j]-'A']);
				dfs(i, j, initmask, 10);
				sort(vis.begin(), vis.end());
				vis.erase(unique(vis.begin(), vis.end()), vis.end());
				for(int k=0; k<(int)vis.size(); k++) {
					res+=(ll)cnt[vis[k]]*cnt[allmask^vis[k]^initmask];
				}
				for(int k=0; k<(int)vis.size(); k++) cnt[vis[k]]=0;
			}
		}

		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111115