Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2010-12-21SRM491 Div1

SRM491 Div1 250 FoxMakingDice

| 22:46 | SRM491 Div1 250 FoxMakingDice - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM491 Div1 250 FoxMakingDice - SRM diary(Sigmar) SRM491 Div1 250 FoxMakingDice - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

何となく対向面の合計値でイテレートすれば解けそうな気がする

・・・と思いつつ今日は眠い・・考えがまとまらない・・・

とにかく書いてみる

うん、合計値をsumとすると、可能な組み合わせは、

(1,sum-1)、(2,sum-2)、・・・、(sum-1,1)となる

(1,sum-1)と(sum-1,1)など重複するものを除くと、可能な組み合わせは(sum-1)/2個である

(sum-1)/2個から3個選ぶ組み合わせについて、並べ方が2通りある(サンプル0から分かる)ので、

C((sum-1)/2, 3)*2が答えか

→書いた

→サンプル2以降が合わない

全然違った

そもそも(1,sum-1)から始まらないパターンがある

たとえばN=8、sum=10とかだと、(1,9)というパターンはなく、(2,8)から(8,2)までになる

つまり、Nがsum-1より小さい場合は、組み合わせ数は重複を含めてN-((sum-1)-N)になる

→書きなおす

→サンプル合わない

あれ?

なぜだ・・

・・・

あ、2箇所書きなおさないといけないのに1箇所だけ直してた。あほか・・

→直す

→サンプル合う

→提出

随分時間かかっちゃったな・・何とか600を解かねば・・・

→600へ


システムテスト

Passed


ソースコード

ll cmb(ll n, ll k) {
	ll result=1;
	ll i, k_=min(k, n-k);

	if(n<0 || n<k || k<0) return 0;
	for(i=1; i<=k_; i++) {
		result*=n-i+1;
		result/=i;
	}

	return result;
}
class FoxMakingDice {
public:
	long long theCount(int N, int K) {
		long long res=0;

		if(N<6) return 0;
		for(int sum=K; sum<=N+N-5; sum++) {
			int m=sum-1;
			if(N<sum-1) m=N-((sum-1)-N);
			if(m/2<3) continue;
			res+=cmb(m/2, 3)*2;
		}
		return res;
	}
};

SRM491 Div1 600 PrefixTree

| 22:46 | SRM491 Div1 600 PrefixTree - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM491 Div1 600 PrefixTree - SRM diary(Sigmar) SRM491 Div1 600 PrefixTree - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

どうせ解けないだろうなーと思いつつ読んでみる

あれ、意外と簡単そうなビットDP

ビットでプレフィクスを共有する集合を管理して、分岐のときに集合を分割すれば良いよね・・

集合さえ決まれば、どこで分岐するかはGreedyに一致するノードを全て結合してやれば決まるはずだ・・


f:id:jackpersel:20101221223839p:image:right

例えばabce,abcf,abdの3つのwordがあったとする

この3つの共通部分a,bを結合すると、残りはce,cf,dとなる

残りの3つの最適な組み合わせ方は通常は分からないので、全探索する

(結果的には、(ce,cf),(d)の分け方をしたときに最適となる)

ce,cfの結合については、元のwordのabceとabcfの共通部分結合をすれば良い(これによりメモ化空間を節約できる)

abcが結合できて、e,fが残る

事前にabまで(2文字目まで)は結合が終わっているという情報を渡しておけば、プラス1文字結合できたことが分かる

ということをメモ化しながら再帰すれば解が出るはずである


とりあえず書いてみるか・・

→(約30分後)

→できた→サンプル通った

・・・

→普通に計算すると、このコードだと最悪計算量が3^16*50くらいなのだが・・

→50の部分は理論上はニアリー1になるはずなので大丈夫なはず。(←大丈夫じゃなかった。ニアリー4くらいになるみたい)

提出


一応900も見るか

難しい・・・だめっぽい

終了


インターミッション

チャレンジのケースとしてあるとすればTLEか・・

一応、最大ケース作っておこう

折角作ったから自分のもテストしとこうかな

TLE

おお・・・まじで・・・・・・終わった・・・

何でコーディングフェーズ中に試さなかったんだ

TLEと分かっていればメモ化から50を消去する方法も考えてたのに。あほすぎる

使えそうなチャレンジケースができたのが救いか


チャレンジフェーズ

自分と似たようなコードを3人ほど発見

誰も落とさない・・微妙に自分のと違うし、自分の600が落ちるのが分かっているので

失敗したら大ダメージだ・・・どうするか

しかし成功すれば非常に大きい気がするので突撃

→成功

きたこれ

あとの2つも撃墜

150点もゲットした。600の提出者はあと2人いるが何か計算量大丈夫そうなのでやめとこう・・


システムテスト

予想通りFailed

Room内で7人提出して1人だけPassでした


後で

計算量を修正

といっても数行で直せる程度の内容なので本当にもったいなかった・・

以下ソースコードです

システムテスト通過版

int memo[1<<16];
int memo2[1<<16];

class PrefixTree {
public:
	int n;
	vector <vector <int> > lcnt;
	vector <string> words;

	//wordsの集合maskに対し深さd以降のノード数を求める
	//この関数は集合maskが深さd以降でしか分岐しないことを前提としている
	int rec(int mask, int d) {
		int res=1000000000;

		//深さ0で分岐したときのノード数をmemoに記録する
		if(memo[mask]>=0) return memo[mask]-d;

		//残り1wordなら残りの文字数を返す
		if(__builtin_popcount(mask)==1) {
			for(int i=0; i<n; i++) {
				if(mask&(1<<i)) {
					res=words[i].size()-d;
					memo[mask]=res+d;
					return res;
				}
			}
		}

		//集合maskの共通文字数をsnodeとする(memo2で記憶する)
		int snode=0;
		if(memo2[mask]>=0) snode=memo2[mask];
		else {
			for(int i=0; i<26; i++) {
				int maxcnt=100;
				for(int j=0; j<n; j++) {
					if(!(mask&(1<<j))) continue;
					maxcnt=min(maxcnt, lcnt[j][i]);
				}
				snode+=maxcnt;
			}
			memo2[mask]=snode;
		}

		//集合maskを深さsnodeで2つに分割し、再帰的に計算する
		for(int i=(mask-1)&mask; i>0; i=(i-1)&mask) {
			int nmask=mask^i;
			res=min(res, rec(i, snode)+rec(nmask, snode)+snode-d);
		}

		memo[mask]=res+d;
		return res;
	}

	int getNumNodes(vector <string> words) {
		int res;

		memset(memo, -1, sizeof(memo));
		memset(memo2, -1, sizeof(memo2));
		n=words.size();
		this->words=words;
		lcnt.clear();
		//lcntには各wordの各a~zの文字数を記憶する
		for(int i=0; i<n; i++) {
			vector <int> vi(26, 0);
			for(int j=0; j<(int)words[i].size(); j++) {
				vi[words[i][j]-'a']++;
			}
			lcnt.push_back(vi);
		}
		res=rec((1<<n)-1, 0)+1;
		return res;
	}
};

以下TLE版(提出時のソース)

int memo[1<<16][52];//この52がまずい
int memo2[1<<16];

class PrefixTree {
public:
	int n;
	vector <vector <int> > lcnt;
	vector <string> words;

	int rec(int mask, int d) {
		int res=1000000000;

		if(memo[mask][d]>=0) return memo[mask][d];

		if(__builtin_popcount(mask)==1) {
			for(int i=0; i<n; i++) {
				if(mask&(1<<i)) {
					res=words[i].size()-d;
					memo[mask][d]=res;
					return res;
				}
			}
		}

		int snode=0;
		if(memo2[mask]>=0) snode=memo2[mask];
		else {
			for(int i=0; i<26; i++) {
				int maxcnt=100;
				for(int j=0; j<n; j++) {
					if(!(mask&(1<<j))) continue;
					maxcnt=min(maxcnt, lcnt[j][i]);
				}
				snode+=maxcnt;
			}
			memo2[mask]=snode;
		}

		//maskが同一ならdによらずsnodeは等しいので、maskに対応するdの種類は1個に近いと予想していた
		for(int i=(mask-1)&mask; i>0; i=(i-1)&mask) {
			int nmask=mask^i;
			res=min(res, rec(i, snode)+rec(nmask, snode)+snode-d);
		}

		memo[mask][d]=res;
		return res;
	}

	int getNumNodes(vector <string> words) {
		int res;

		memset(memo, -1, sizeof(memo));
		memset(memo2, -1, sizeof(memo2));
		n=words.size();
		this->words=words;
		lcnt.clear();
		for(int i=0; i<n; i++) {
			vector <int> vi(26, 0);
			for(int j=0; j<(int)words[i].size(); j++) {
				vi[words[i][j]-'a']++;
			}
			lcnt.push_back(vi);
		}
		res=rec((1<<n)-1, 0)+1;
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20101221