Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-01-13SRM493 Div1

SRM493 Div1 300 StonesGame

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

Problem Statement

コーディングフェーズ

これはmin-maxゲーム木ぽい?

状態数100万・・・まあ大丈夫だろう(←大間違い)

書いてみた

→stack overflow

あー無限ループしている

サンプルを見直すと無限ループはDrawなのか・・

ふむ・・勝ち負けの2値ではなくDrawを含む3値にすれば良いかな

訪問済の状態を配列で記憶して・・

書けた

サンプル通った

と思ったら4以降通ってない

stack overflowしてる

あ、そうか・・そりゃそうだよな・・深さ100万のDFSじゃオーバーフローして当たり前だ

そんなこと最初に気づけよ・・・何で気付かなかったんだ・・

ってどうするんだ・・

・・・

・・・

min-maxじゃ解けないのか、もしかして

今更そんなことに気づいてもすでに30分経過してるんだが・・・

だめだ

はまるパターンだ

諦めて450を解こう

450はきっと簡単に違いない

→450へ


後で

結局450終わったあとも良くわからなかったがチャレンジフェーズでようやく2ターンしか考えなくていいことに気づいた

ということで解いてみた

2ターンのみと分かっても結構条件がややこしく、難しい

個人的には450より難しい・・・


ソースコード

class StonesGame {
public:
	int N, K;

	//p1からp2へ1回の移動で到達できるか
	bool cango(int p1, int p2) {
		if(p2>p1) swap(p1, p2);
		if((p1-p2)%2==K%2) return false;//距離がKと偶奇が等しいと到達できない
		if(p1-p2>K-1) return false;//距離がK-1以上だと到達できない
		int d=(p2-(p1-K+1))/2;
		if(p1-K+1+d<0 || p1+d>=N) return false;//反転する範囲が0~N-1をはみだすと到達できない
		return true;
	}

	string winner(int N, int M, int K, int L) {
		this->K=K;
		this->N=N;
		M--; L--;
		if(cango(M, L)) return "Romeo";
		for(int p=0; p<N; p++) {
			if(cango(M, p) && !cango(p, L)) return "Draw";
		}

		return "Strangelet";
	}
};

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