Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-08-10SRM514 Div1

SRM514 Div1 250 MagicalGirlLevelOneDivOne

| 15:56 | SRM514 Div1 250 MagicalGirlLevelOneDivOne - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM514 Div1 250 MagicalGirlLevelOneDivOne - SRM diary(Sigmar) SRM514 Div1 250 MagicalGirlLevelOneDivOne - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

どう見ても探索できそうにないので一発で求める方法を考える

ちょっと試してみると、nが偶数の場合は、右下、右上、左下みたいな3手でn-2のときと同じ動きができる。ということはn==0で上下左右4方向に1歩動くことが可能なので偶数のnがあれば絶対たどり着ける。

じゃあ奇数はどうかというと、(x+y)%2が常に同じところにしか行けないので、それで判定する。同じようにn-2のときと同じ動きができるので、少なくとも斜め4方向には進めるから(x+y)%2が0ならYES。そうでなければNO。

(x+y)%2の判定はちょっと知識問題チックだなと思った。

ところでxやyはマイナスがありうるので、(x+y)%2がとりうる値は実は-1,0,1の3つある。サンプルは-1になるものがないのでチャレンジポイントになる。x%2==y%2という判定をしている人を2人落とした(何とコーディングフェーズの上位2人がそのような凡ミスを・・)。ラッキーでした。


ソースコード

class MagicalGirlLevelOneDivOne {
public:
	string isReachable(vector <int> jump, int x, int y) {
		int n=jump.size();
		for(int i=0; i<n; i++) {
			if(jump[i]%2==0) return "YES";
		}
		int r=(x+y)%2;
		if(r==0) return "YES";
		return "NO";
	}
};

SRM514 Div1 600 MagicalGirlLevelTwoDivOne

| 15:56 | SRM514 Div1 600 MagicalGirlLevelTwoDivOne - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM514 Div1 600 MagicalGirlLevelTwoDivOne - SRM diary(Sigmar) SRM514 Div1 600 MagicalGirlLevelTwoDivOne - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

oddかどうかの判定なので、まず偶奇だけ覚えればいい

ということで全部0,1に変換する

さらにn, mが最大10しかないのがポイント

c~c+m-1までのparityは1でなければならないが、c+1~c+mまでのparityも同様に1でなければならない

従ってcとc+mの偶奇は等しい。ということは、01に変換した行は、必ずm個ごとに循環する繰り返しパターンとなる。

縦についても同様。なので、m列分の縦のparityを記憶するDPが可能。


で方針はすぐ立ったけどコーディングに45分かけてもデバッグしきれなかった。

何か繰り返しパターンをビット化したのだけども、右端にはみ出す部分の処理がうまく行かなかった。

もうちょっとコーディングがまともにできるようになりたい・・・・・


ソースコード

修正済みです

const int MOD=1000000007;
int dp[11][1<<10];

class MagicalGirlLevelTwoDivOne {
public:
	int theCount(vector <string> pal, int n, int m) {
		int res;
		int h=pal.size(), w=pal[0].size();
		ll rows[52], brows[52]; //rows-> 行の偶奇をビット化、brows-> 行のうちbrokenのものを1としてビット化
		for(int i=0; i<h; i++) {
			rows[i]=0;
			for(int j=0; j<w; j++) {
				if(pal[i][j]=='.') continue;
				if((pal[i][j]-'0')%2==1) rows[i]|=(1LL<<j);
			}
			brows[i]=0;
			for(int j=0; j<w; j++) {
				if(pal[i][j]=='.') brows[i]|=(1LL<<j);
			}
			for(int j=w; j<60; j++) {
				brows[i]|=(1LL<<j);
			}
		}

		//行iに対し偶奇パターンparが使用可能かどうかの判定
		int parok[10][1<<10];
		for(int i=0; i<n; i++) {
			for(int par=0; par<(1<<m); par++) {
				bool ok=true;
				if((__builtin_popcountll(par)&1)==0) ok=false;
				for(int k=0; m*k<w; k++) {
					for(int l=0; i+n*l<h; l++) {
						ll diff=((par^(rows[i+n*l]>>(m*k)))&((1LL<<m)-1))<<(m*k);
						if((diff|brows[i+n*l])!=brows[i+n*l]) {
							ok=false;
							break;
						}
					}
					if(!ok) break;
				}
				if(ok) parok[i][par]=1;
				else parok[i][par]=0;
			}
		}

		//行iに対し偶奇パターンparのときのパターン数
		int mul[52][1<<10];
		for(int i=0; i<n; i++) {
			for(int par=0; par<(1<<m); par++) {
				mul[i][par]=1;
				for(int k=0; i+k*n<h; k++) {
					for(int j=0; j<w; j++) {
						if(brows[i+k*n]&(1LL<<j)) {
							if(par&(1LL<<(j%m))) mul[i][par]=(ll)mul[i][par]*5%MOD;
							else mul[i][par]=(ll)mul[i][par]*4%MOD;
						}
					}
				}
			}
		}

		memset(dp, 0, sizeof(dp));
		dp[0][0]=1;
		for(int i=0; i<n; i++) {
			for(int mask=0; mask<(1<<m); mask++) {
				for(int par=0; par<(1<<m); par++) {
					if(!parok[i][par]) continue;
					int nmask=mask^par;
					dp[i+1][nmask]=((ll)dp[i+1][nmask]+dp[i][mask]*(ll)mul[i][par])%MOD;
				}
			}
		}

		res=dp[n][(1<<m)-1];
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110810