Hatena::Grouptopcoder

yuyarinのtopcoder記

TopCoder, Google Code JamPKU JudgeOnlineICPC などのアルゴリズム系プログラミングコンテストの参加や練習の記録を残していきます.

アルゴリズムやテーマで分類した目次はこちら

2010/05/27

Google Code Jam 2010 Round 1A C. Number Game

| 18:46

問題

黒板に A, B 2つの数字がかかれていて,2人のプレイヤーこの数字を使ってゲームを行う. プレイヤーは交互に数字 A を A-k*B に置き換えるか,数字 B を B-k*A に置き換える操作をする. k は正数である.これを交互に行っていき,数字を 0 以下にしてしまった方が負けである.このゲームの初期値に対する先攻の必勝パターンの数を範囲 A∈[A1,A2] B∈[B1,B2] において求める.

アプローチ(再帰

とりあえず再帰を使って単純に実装してみる.

using namespace std;
typedef long long ll;

#define For(i,a,b)    for(int i=(a);i<(b);++i)
#define Rep(i,n)      for(int i=0;i<(n);++i)

// 必ず a>=b
// p==true: player が先攻
// 先攻のプレイヤーが必勝の場合は true を返す
bool rec(int a, int b, bool p)
{
	if(b<=0) return !p;
	For(k,1,(a-1)/b+1)
		if(rec(max(a-k*b,b),min(a-k*b,b),!p)==p) return p;
	return !p;
}

int main(void)
{
	int T;
	cin >> T;
	
	Rep(t,T)
	{
		int A1, A2, B1, B2;
		cin >> A1 >> A2 >> B1 >> B2;
		ll r = 0;
		For(a,A1,A2+1) For(b,B1,B2+1)
			if(rec(max(a,b),min(a,b),true)) r++;
		cout << "Case #" << t+1 << ": " << r << endl;
	}
}

sample は通るけど最大のケース,たとえば (A, B) = (1000000,1) だとスタックが足りなくなって落ちる*1ことや,そもそも計算が終わらないだろうことが容易に想像がつく.また,1,000,000 x 1,000,000 の配列を用意しておくのもメモリサイズの制約上厳しい.VSIZE 3728GB って...

http://www.yuyarin.net/screenshot/20100527152740.png

なので数学的に解を出す方向で考えてみる.

アプローチ(数学

ひとまず 50x50 ぐらいで出力してみると,傾向があるのがわかる.

↓A B→
 *************************************************
*  ***********************************************
*   **********************************************
**    ********************************************
***     ******************************************
***      *****************************************
****       ***************************************
****        **************************************
*****         ************************************
******          **********************************
******           *********************************
*******            *******************************
********             *****************************
********              ****************************
*********               **************************
*********                *************************
**********                 ***********************
***********                  *********************
***********                   ********************
************                    ******************
************                     *****************
*************                      ***************
**************                       *************
**************                        ************
***************                         **********
****************                          ********
****************                           *******
*****************                            *****
*****************                             ****
******************                              **
*******************                               
*******************                               
********************                              
*********************                             
*********************                             
**********************                            
**********************                            
***********************                           
************************                          
************************                          
*************************                         
*************************                         
**************************                        
***************************                       
***************************                       
****************************                      
*****************************                     
*****************************                     
******************************                    
******************************                    

A > αB の場合と B > αA の場合に必勝パターンであることが分かる.このαを求める.

A, B は対称性があるので A > B の場合のみを考えれば良い(A==B の場合は先手が必ず負ける).

まず A >= 2B の場合に必勝パターンであることは簡単にわかる.が,よく見ると傾きは 2 より若干小さい.(11,6) -> A:(5,6) -> B:(5,1) -> A(1,1) -> B:(1,0) と A < 2B でも A が必ず勝てる組が存在する.A >= 2B の場合に必勝パターンであるということは先に選択肢を持った方が必ず勝つということである.

なのでどちらも選択肢が 2 つ以上持てないギリギリのパターンを考えると,(1,1) <- (2,1) <- (3,2) <- (5,3) <- (8,5) <- ... という組の列になる.この列はフィボナッチ数列になっている.このとき A と B の比はフィボナッチ数列の隣接項の比,黄金比 Φ=(sqrt(5.0)+1)/2 ≒ 1.6 である.よって A > ΦB であれば必勝パターンであることがわかる.

B をある値 b に固定したときに A > Φb であればよい.[A1, A2] でこのようになる A の個数は max(0,A2-max(A1,Φb)+1) である.これを b∈[B1, B2] の範囲で調べた後,A, B を反対にした場合の数を調べれば良い.

ソースコード

答えとなる数値は最大で 1M x 1M であるから int だとオーバーフローするので long long を使用する.

#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <cmath>

typedef long long ll;

using namespace std;

#define For(i,a,b)    for(int i=(a);i<(b);++i)
#define Rep(i,n)      for(int i=0;i<(n);++i)

double golden = (sqrt(5.0)+1)/2;

ll solve(int A1, int A2, int B1, int B2)
{
	ll r = 0;
	For(b,B1,B2+1)
		r += max(0,A2-max(A1,int(b*golden)+1)+1);
	return r;
}

int main(int argc, char* argv[])
{
	int T;
	cin >> T;
	
	Rep(t,T)
	{
		int A1, A2, B1, B2;
		cin >> A1 >> A2 >> B1 >> B2;
		ll r = solve(A1, A2, B1, B2) + solve(B1, B2, A1, A2);
		cout << "Case #" << t+1 << ": " << r << endl;
	}
	
	return 0;
}

*1Mac OS X ではデフォルトで 8192 KB なので 10 万回ぐらいめの再帰で溢れてしまう.

VadimVadim 2012/07/09 23:30 Articles like this are an example of quick, hlepful answers.

qjbrhhqjbrhh 2012/07/10 15:49 kSuNdQ <a href="http://mdjoejftmbvz.com/">mdjoejftmbvz</a>

pqzkpfjtrpqzkpfjtr 2012/07/10 21:46 qQr9EH , [url=http://fhvkqwxahzhs.com/]fhvkqwxahzhs[/url], [link=http://mdchxyyvtvey.com/]mdchxyyvtvey[/link], http://rqniilnhuwie.com/

oidakxcccinoidakxcccin 2012/07/12 12:07 Jpayqp <a href="http://jyiazemeadxh.com/">jyiazemeadxh</a>

whmpyvpwhmpyvp 2012/07/12 17:36 VAQd8L , [url=http://gqopwfgotuey.com/]gqopwfgotuey[/url], [link=http://lfdyxzapnxeq.com/]lfdyxzapnxeq[/link], http://kqvfxprmucse.com/

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/yuyarin/20100527