Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-09-20SRM519 Div1

SRM519 Div1 250 BinaryCards

| 00:43 | SRM519 Div1 250 BinaryCards - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM519 Div1 250 BinaryCards - SRM diary(Sigmar) SRM519 Div1 250 BinaryCards - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

AとBをビット単位で上の桁から見ていき、最初にAとBのビットが異なるところより下位のビットを全て1にすれば良さそう

何となくビットをvectorに落としたらコードが汚くなった。。。

普通にビット演算すれば良かった


ソースコード

class BinaryCards {
public:
	long long largestNumber(long long A, long long B) {
		long long res;

		ll a=A, b=B;
		vector <int> ra, rb;
		while(a) {
			ra.push_back(a%2);
			a/=2;
		}
		while(b) {
			rb.push_back(b%2);
			b/=2;
		}

		int n=max(ra.size(), rb.size());
		for(int i=ra.size(); i<n; i++) {
			ra.push_back(0);
		}
		for(int i=rb.size(); i<n; i++) {
			rb.push_back(0);
		}
		reverse(ra.begin(), ra.end());
		reverse(rb.begin(), rb.end());

		vector <int> resv;
		int firstdiff=n;
		for(int i=0; i<n; i++) {
			if(ra[i]!=rb[i]) {firstdiff=i; break; }
			resv.push_back(rb[i]);
		}
		for(int i=firstdiff; i<n; i++) {
			resv.push_back(1);
		}

		res=0;
		for(int i=0; i<n; i++) {
			res*=2;
			res+=resv[i];
		}
		return res;
	}
};

SRM519 Div1 600 RequiredSubstrings

| 00:43 | SRM519 Div1 600 RequiredSubstrings - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM519 Div1 600 RequiredSubstrings - SRM diary(Sigmar) SRM519 Div1 600 RequiredSubstrings - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

DPぽい

n文字目まで進んだところで、ビットマスクでwordsの要素のうち登場したものを覚えておけば良さそう

しかしその時点で未登場のwordsのprefixが末尾に出てきている場合はそれを状態として持たなければならない・・・

当然26文字^50乗では爆発する。各wordsのprefix文字数で何文字目まで一致するか覚えると50文字^6乗でやはり無理。

・・・

・・・

よく考えると各wordsの一致prefix文字数を覚える必要はない。最長の一致prefix文字数を持つwordsだけ覚えておけば、後は自動的に決まる。

しかしこれはコーディングが・・・きつそう・・・

他に思いつかないのでとりあえず書いてみる。やっぱり時間内に書ける内容ではなかった。

もっと単純に書けるように思考の転換が必要です。


ソースコード

とりあえず上記方針でpractice通ったもの

prefixが一致しなくなった時点で何文字目まで一致するか調べるためkmp法とか導入していてややこしいです

const int MOD=1000000009;

int dp[52][1<<6][6][52];

class RequiredSubstrings {
public:
	int solve(vector <string> words, int C, int L) {
		int res;
		int n=words.size();

		//maxlenidx番目のwordsの後ろmaxlen文字が、他のwordsの最長何文字のprefixになるか
		int preflen[6][52][6];
		memset(preflen, 0, sizeof(preflen));
		for(int maxlenidx=0; maxlenidx<n; maxlenidx++) {
			for(int maxlen=0; maxlen<(int)words[maxlenidx].size(); maxlen++) {
				string mpref=words[maxlenidx].substr(0, maxlen);
				for(int i=0; i<n; i++) {
					for(int j=1; j<=min(maxlen, (int)words[i].size()-1); j++) {
						if(words[i].substr(0, j)==mpref.substr(maxlen-j)) preflen[maxlenidx][maxlen][i]=j;
					}
				}
			}
		}

		//kmp法のnextテーブル
		vector <int> next[6];
		for(int k=0; k<n; k++) {
			next[k].assign(words[k].size()+1, -1);
			int i, j;
			for(i=0, j=-1; i<(int)words[k].size(); i++, j++, next[k][i]=j) {
				while((j>=0) && (words[k][i]!=words[k][j])) j=next[k][j];
			}
		}

		memset(dp, 0, sizeof(dp));
		dp[0][0][0][0]=1;
		for(int d=0; d<L; d++) {
			for(int mask=0; mask<(1<<n); mask++) {
				for(int maxlenidx=0; maxlenidx<n; maxlenidx++) {
					for(int maxlen=0; maxlen<(int)words[maxlenidx].size(); maxlen++) {
						if(dp[d][mask][maxlenidx][maxlen]==0) continue;
						for(char c='a'; c<='z'; c++) {
							int nmask=mask;
							int nmaxlenidx=0, nmaxlen=0;
							for(int i=0; i<n; i++) {
								if(c==words[i][preflen[maxlenidx][maxlen][i]]) {
									if(preflen[maxlenidx][maxlen][i]+1==(int)words[i].size()) {
										nmask|=(1<<i);
									} else {
										if(preflen[maxlenidx][maxlen][i]+1>nmaxlen) {
											nmaxlenidx=i;
											nmaxlen=preflen[maxlenidx][maxlen][i]+1;
										}
									}
								} else {
									int tmaxlen=preflen[maxlenidx][maxlen][i];
									while(tmaxlen>=0 && words[i][tmaxlen]!=c) tmaxlen=next[i][tmaxlen];
									tmaxlen++;
									if(tmaxlen>nmaxlen) {
										nmaxlenidx=i;
										nmaxlen=tmaxlen;
									}
								}
							}
							dp[d+1][nmask][nmaxlenidx][nmaxlen]=((ll)dp[d+1][nmask][nmaxlenidx][nmaxlen]+dp[d][mask][maxlenidx][maxlen])%MOD;
						}
					}
				}
			}
		}

		res=0;
		for(int mask=0; mask<(1<<n); mask++) {
			if(__builtin_popcountll(mask)!=C) continue;
			for(int maxlenidx=0; maxlenidx<n; maxlenidx++) {
				for(int maxlen=0; maxlen<(int)words[maxlenidx].size(); maxlen++) {
					res=((ll)res+dp[L][mask][maxlenidx][maxlen])%MOD;
				}
			}
		}

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