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";
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110113