Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2010-05-22Google Code Jam 2010 Round 1A

Google Code Jam 2010 Round 1A C Number Game

| 21:50 | Google Code Jam 2010 Round 1A C Number Game - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam 2010 Round 1A C Number Game - SRM diary(Sigmar) Google Code Jam 2010 Round 1A C Number Game - SRM diary(Sigmar) のブックマークコメント

Problem Statement

各問題のポイントを見て、BとCがポイントが小さかったのでCから取り掛かりました。

少し考えて、Nimの一種だということはすぐに分かりました。この種のゲームでは、先にkの値を複数から選択できるほうがゲームの主導権を握り、100%勝つことになります。

A>Bの場合について考えます。(B>Aの場合は、AとBを反転させれば良い。A==Bは必ず先手が負けるので、考慮する必要がない)

A/2>=Bのとき、最初から取りうるkの値が2種類以上となり、先手が勝ちます。また、(2/3)A<=Bのとき、1ターン目で後手が必ず取りうるk>=2となり、後手が勝ちます。では、(2/3)A>B>A/2のとき、どうなるでしょうか。。。

ここらまで考えて、30分くらい経ちました。ポイント的には簡単な問題のはずなのに随分時間がかかってしまっているなと思い、スコアボードを見ると、small/largeがそれぞれ5点/10点だったはずの問題Cが、16点/25点に変わってます。え・・・。Googleさん・・・。一番難しい問題を最初に解いてた・・・・・・。

ここまで来て別の問題に行くと忘れてしまいそうなので、このまま突き進むことにしました。

話を戻すと、今までは1ターン目でどちらかが主導権を握れるパターンしか考えていませんでした。では、誰も主導権を握れないままに終わるパターンはどのようなパターンかと考えると、、、

(B,A)=(1,1),(1,2),(2,3),(3,5),(5,8),(8,13),(13,21),・・・

つまり、AとBがa_(n+2)=a_(n+1)+a_nの数列の隣同士となるときに、最後までどちらも主導権を握れないパターンになります。これは、明らかにフィボナッチ数列です。

しかし、これが分かったから何なんでしょう。もう少し色々試してみました。いくつかのフィボナッチ数列のペアを使って、Aの値を固定したままBの値を少しずつ増やしたり、減らしたりしてゲームをシミュレーションしてみます。すると、Bの値を増やせば増やすほど、後手が早いターンで主導権を握れるようになります。また、逆にBの値を減らせば減らすほど、先手が早いターンで主導権を握れるようになることが見えてきました。

これ以上厳密な証明はしませんでしたが、フィボナッチ数列の隣同士の値の比率を計算してみると、約0.618になるので(黄金比になるんですね)、B=0.618Aくらいに先手が勝つか、後手が勝つかの境界があるらしきことは間違いなさそうです。

あとは、マシンパワーで何とでもなるレベルです。1~1000000までの全てのAに対して、先手が勝つBの最大値を求めます。仮に最大値をA*0.618とおいてシミュレーションし、先手が勝てば最大値を増やして先手が負けるまでシミュレーションします。最大値がA*0.618のときに後手が勝てば、先手が勝つまで最大値を減らしていきます。

全てのAに対し先手が勝つBの最大値が分かれば、あとは全ての取りうるAに対して先手が勝つパターン数を合計するだけです。

結局、提出まで1時間半もかかってしまいました。Small、Largeともに通ったので、良かったです。。

以下、ソースです。(少し体裁を手直ししてます)


typedef long long ll;

class GCJ {
public:
	int lim[1000002];

	ll solve(int a1, int a2, int b1, int b2) {
		ll result=0;
		
		for(int i=a1; i<=a2; i++) {
			result+=max(min(lim[i], b2)-b1+1, 0);
		}
		for(int i=b1; i<=b2; i++) {
			result+=max(min(lim[i], a2)-a1+1, 0);
		}

		return result;
	}

	bool ifw(int a, int b) {//ゲームのシミュレーション関数
		bool w=true;
		if(a==b) return false;
		while(b) {
			if(a>=b*2) return w;
			a-=b;
			swap(a, b);
			w=!w;
		}
		return w;
	}

	void calcl(void) {//全てのAに対し、先手が勝つBの最大値を計算
		int l;
		for(int i=1; i<=1000000; i++) {
			l=i*0.618;
			if(ifw(i, l)) {
				while(1) {
					l++;
					if(!ifw(i, l)) break;
				}
				lim[i]=l-1;
			} else {
				while(1) {
					l--;
					if(ifw(i, l)) break;
				}
				lim[i]=l;
			}
		}
	}
};

int main() {
	ofstream ofs("output.txt");
	ifstream ifs("C-large.in.txt");
	int n, A1, A2, B1, B2;
	GCJ gcj;

	gcj.calcl();
	ifs >> n; ifs.ignore();
	for(int i=1; i<=n; i++) {
		ifs >> A1 >> A2 >> B1 >> B2;
		ofs << "Case #" << i << ": " << gcj.solve(A1, A2, B1, B2) << endl;
	}
}
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20100522