Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2012-02-10SRM532 Div1

SRM532 Div1 300 DengklekMakingChains

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

Problem Statement

コーディングフェーズ

3つとも数字のやつを全部足しあわせておいて、左と右に適当にくっつければいいんじゃないのか?

書いた

合わない。.7.とかサンプルにあった。親切すぎ!!

よく考えると300だしなあ。他にもコーナーケースがありそうだ。

要素数1のサンプルがない。なるほど。危ない・・・修正修正

あとは大丈夫かな・・

提出


ソースコード

class DengklekMakingChains {
public:
	int maxBeauty(vector <string> chains) {
		int res=0;
		int n=chains.size();

		int used[52];
		memset(used, 0, sizeof(used));
		int base=0;
		for(int i=0; i<n; i++) {
			bool ok=true;
			int cnt=0;
			for(int j=0; j<3; j++) {
				if(chains[i][j]=='.') ok=false;
				else cnt+=chains[i][j]-'0';
			}
			if(ok) {
				base+=cnt;
				used[i]=1;
			}
		}

		res=base;

		for(int i=0; i<n; i++) {
			if(used[i]) continue;
			int cnti=0;
			for(int k=2; k>=0; k--) {
				if(chains[i][k]=='.') break;
				cnti+=chains[i][k]-'0';
			}
			res=max(res, base+cnti);
			for(int j=0; j<n; j++) {
				if(used[j]) continue;
				if(i==j) continue;
				int cntj=0;
				for(int k=0; k<3; k++) {
					if(chains[j][k]=='.') break;
					cntj+=chains[j][k]-'0';
				}
				res=max(res, base+cnti+cntj);
			}
			cnti=0;
			for(int k=0; k<3; k++) {
				if(chains[i][k]=='.') break;
				cnti+=chains[i][k]-'0';
			}
			res=max(res, base+cnti);
			res=max(res, chains[i][1]-'0');//'.'は'0'より小さい・・・
		}

		return res;
	}
};

SRM532 Div1 450 DengklekBuildingRoads

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

Problem Statement

コーディングフェーズ

なんだこりゃ。典型的なDP。簡単すぎないか?

K<=8だから直前8個まで+今見てるの1個で9個の偶奇を覚えておけばいいだろう

DPの更新時は、直前8個のどれかと今見てる人をくっつけて道を1つ増やすか、見る人を次に進めるかの2パターン

書いた。

合わない。

しかも間違いが分からない。簡単と思いきや訳わからん・・・

・・・

分かった。道を追加するのに、順番を考慮していないから同じパターンを2回以上数えている。

直前に追加した道を直前8個の誰に対して追加したかを覚えるように変更

できた。

合った。

提出。

結構時間かかった・・・450の割に難しい。。


ソースコード

//dp[今見てる人][追加した道の数][直前に追加した道の相手][直前8個+今見てる人の偶奇]
int dp[32][32][9][1<<9];

const int MOD=1000000007;

class DengklekBuildingRoads {
public:
	int numWays(int N, int M, int K) {
		int res;

		memset(dp, 0, sizeof(dp));
		dp[0][0][0][0]=1;
		for(int p=0; p<N; p++) {
			for(int b=0; b<=M; b++) {
				for(int last=K-1; last>=0; last--) {
					for(int mask=0; mask<(1<<(K+1)); mask++) {
						if(b<M) {
							for(int i=max(0, p-1-last); i<p; i++) {
								int nmask=mask^(1<<(p-i))^1;
								dp[p][b+1][p-1-i][nmask]=((ll)dp[p][b+1][p-1-i][nmask]+dp[p][b][last][mask])%MOD;
							}
						}
						if(!(mask&(1<<K))) {
							int nmask=(mask<<1);
							dp[p+1][b][K-1][nmask]=((ll)dp[p+1][b][K-1][nmask]+dp[p][b][last][mask])%MOD;
						}
					}
				}
			}
		}
		res=0;
		for(int i=0; i<K; i++) {
			res=((ll)res+dp[N][M][i][0])%MOD;
		}
		
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20120210