Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-01-13SRM493 Div1

SRM493 Div1 450 AmoebaCode

| 00:04 | SRM493 Div1 450 AmoebaCode - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM493 Div1 450 AmoebaCode - SRM diary(Sigmar) SRM493 Div1 450 AmoebaCode - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

いかにもDP

普通にやれば・・7^50 明らかに無理

やっぱりここは7という数字がいかにも何かありそうですよね

7・・・うーん・・

7種類しか数字がないわけだから、鳩の巣原理で解は最大7か。

これだ!

直前の7個だけ覚えとけば良いに違いない

7^7*50だから、約4000万。いけるか・・

状態の表現方法は・・・ビットに収めようとすると、3*7=21ビット必要

しかし2^21*50にすると1億超えるからきついような気がする

・・というか直前6個が異なる数字なら解が7だから覚えるのは6個でいいのか

2^18*50になった。でもまだ厳しい気がしてきた・・

よく考えるとイテレーティブに書くと2^18*50になるがリカーシブに書けばそんなことないのでは

そもそも6個覚える場合は6個とも違う数字でなければ意味がないので、状態は7P6*50=25万くらいしかないんじゃ・・・

これはmap<vector <int>, int>を使っても楽勝な予感。いける。

最初だけ直前6個が存在しないから、SRM483 500(Bribes)の反省を生かして番兵っぽく0を6個並べとこう

→書けた→サンプル通った

一応0を50個試しておこう

一瞬で終わった。大丈夫そう。

→提出


チャレンジフェーズ

誰かが絨毯爆撃したらしく、数分で半分くらいのmediumが落ちた

特に何もできず・・


システムテスト

Passed

いつもmediumは下らないケアレスミスやらで落とすのだが今日はPassしてくれて助かった

今回はeasyが提出できなかったから本当に助かった・・・

easyを適度に諦めたのが功を奏して十分な時間が確保できたのが良かったかな


ソースコード

実は一番計算量が厳しいのは0が49個+最後に7が1個とかのパターンだったみたい

最悪でも1秒ちょいで終わるが思ったより時間がかかった。コストの見積もりを勘違いしたのかそんなもんなのか。。。

あともう少し綺麗に書きたいものです・・

map <vector <int>, int> memo[52];

class AmoebaCode {
public:
	int n, K;
	string code;
	int rec(int d, vector <int> &vi, int tres) {
		int res=0;

		if(d==n) return 1;
		if(memo[d].count(vi)) return memo[d][vi];

		if(code[d]=='0') {
			for(int i=1; i<=K; i++) {
				bool ok=true;
				for(int j=0; j<tres-1; j++) {
					if(vi[j]==i) {
						ok=false;
						break;
					}
				}
				if(ok) {
					vector <int> nvi;
					nvi.push_back(i);
					for(int j=0; j<tres-2; j++) {
						nvi.push_back(vi[j]);
					}
					if(rec(d+1, nvi, tres)) {
						res=1;
						break;
					}
				}
			}
		} else {
			bool ok=true;
			for(int j=0; j<tres-1; j++) {
				if(vi[j]==code[d]-'0') {
					ok=false;
					break;
				}
			}
			if(ok) {
				vector <int> nvi;
				nvi.push_back(code[d]-'0');
				for(int j=0; j<tres-2; j++) {
					nvi.push_back(vi[j]);
				}
				if(rec(d+1, nvi, tres)) {
					res=1;
				}
			}
		}

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

	int find(string code, int K) {
		int res=1;

		n=code.size();
		this->K=K;
		this->code=code;
		for(int i=2; i<=7; i++) {
			for(int j=0; j<52; j++) memo[j].clear();
			vector <int> vi(i-1, 0);
			if(rec(0, vi, i)) res=i;
		}
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110113