Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-11-15SRM523 Div1(Practice)

SRM523 Div1 250 CountingSeries

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

Problem Statement

解答方針

等差数列については割り算で個数を求める

等比数列についてはイテレーションで個数を求める

等比数列をイテレーションする際に、等差数列に含まれるものを除いていけばOK

意外と等差数列を数えるときに、upperBound<aのときの処理を忘れている人が多かったようで、非常に正答率が低かった。

サンプルを信じすぎないことが大事だと思う。


ソースコード

class CountingSeries {
public:
	long long countThem(long long a, long long b, long long c, long long d, long long upperBound) {
		long long res;

		if(upperBound<a) res=0;
		else res=(upperBound-a+b)/b;
		while(c<=upperBound) {
			if(c<a || (c-a)%b!=0) res++;
			c*=d;
			if(d==1) break;
		}
		return res;
	}
};

SRM523 Div1 500 BricksN

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

Problem Statement

解答方針

1つの列について並べ方を列挙していって、再帰的に上に登っていく感じ

連続する空白+連続するブリックで適当に再帰的に並べ方を数えると50^4くらいの計算量になる

もう少し場合分けして工夫すると50^3に落とせるが別にそこまでする必要はない


ソースコード

const int MOD=1000000007;
int memo[52][52];
int memo2[52];

class BricksN {
public:
	int k;

	int countPat(int w) {//幅wの連続するブリックの置き方の場合の数
		if(w==1) return 1;
		if(memo2[w]>=0) return memo2[w];

		int res=0;
		if(k>=w) res++;//幅wのブリックを1つだけ置く場合は再帰すると無限ループになるので別扱いする
		for(int i=1; i<=min(w-1, k); i++) {//次に置くブリックの幅をiとして再帰する
			res=((ll)res+countPat(w-i))%MOD;
		}

		memo2[w]=res;
		return res;
	}

	int rec(int w, int h) {
		if(h==0 || w<=1) return 1;
		if(memo[w][h]>=0) return memo[w][h];

		int res=1;//ブリックを1つも置かない場合のみ別扱いで+1しておく
		//連続する空白→連続するブリックの順に並べる
		for(int i=1; i<=w-1; i++) {//次に連続する空白の数をiとする
			for(int j=1; i+j<=w; j++) {//空白の右側に連続するブリックの数をjとする
				//rec(j+1, h-1)で連続するブリックの上に置く場合の数を算出
				//rec(w-(i+j),h)で連続するブリックの右側に置く場合の数を算出
				res=((ll)res+(ll)countPat(j)*rec(j+1, h-1)%MOD*rec(w-(i+j), h)%MOD)%MOD;
			}
		}

		memo[w][h]=res;
		return res;
	}

	int countStructures(int w, int h, int _k) {
		int res;

		k=_k;
		memset(memo, -1, sizeof(memo));
		memset(memo2, -1, sizeof(memo2));

		//関数recが左端に1つ以上空白を確保するようになっているため、幅を1つ増やして引数とする
		res=rec(w+1, h);
		return res;
	}
};

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