kmjp's blog

競技プログラミング参加記です

Google Code Jam 2019 Round 3 : A. Zillionim

BもDもSmallしか通らないコードだったのに、Submitが速かったせいで変に期待させて申し訳ない…。
https://codingcompetitions.withgoogle.com/codejam/round/0000000000051707/0000000000158f1a

問題

以下のゲームを行う。
初期状態で1~10^12までの数字が1個ずつある。
自分と相手は交互に自分の手番が回ってくる。
両者とも自分の手番では、10^10個連続して残っている数字の列があれば、任意に選択してそれを取り除く。
取り除くことができない場合、その人の負けとなる。
相手があり得る選択肢のうち等確率でいずれかを選択してくるとき、99.8%以上勝ち越すコードを作れ。

解法

面倒なのでD=10^10とする。
相手がランダムに選択してくることを利用し、自分だと選択肢があるけど相手は実質選択肢がないような状況に持ち込もう。
例えば、ちょうど2Dだけ数字が連続しているような箇所を選べば、相手はその範囲を選ぶ場合99.99999999%の確率で1回しか選択できないが、自分は1回と2回どちらを選ぶか選択できる。
よって以下の手順を取る。

  • 3D以上の連続する領域があれば、端を2D残すように選ぶ。
  • [2D+1,3D-1]の長さの領域があれば、適当に消費する。

ここまで済ませると、残りは長さ2Dの領域か2D未満の領域しか残らない。
自分の手番の終了後、残り領域の数が偶数となるよう、2Dの領域を端っこ1Dだけ選ぶか真ん中1D選ぶか適切な方を選び続けよう。

int W;

set<pair<ll,ll>> S;

void hoge(ll p) {
	auto it=S.lower_bound({p,1LL<<60});
	it--;
	auto pa=*it;
	S.erase(it);
	if(pa.first<=p-10000000000LL) {
		S.insert({pa.first,p});
	}
	if(pa.second>=p+20000000000LL) {
		S.insert({p+10000000000LL,pa.second});
	}
}

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	S.clear();
	S.insert({1,1000000000001LL});
	while(1) {
		ll P;
		cin>>P;
		if(P==-1) exit(0);
		if(P<0) break;
		
		hoge(P);
		vector<pair<ll,ll>> V[4];
		FORR(s,S) {
			ll d=s.second-s.first;
			if(d==20000000000LL) V[1].push_back(s);
			else if(d<20000000000LL) V[0].push_back(s);
			else if(d<30000000000LL) V[2].push_back(s);
			else V[3].push_back(s);
		}
		
		ll tar;
		if(V[3].size()) {
			tar=V[3][0].first+20000000000LL;
		}
		else if(V[2].size()) {
			tar=V[2][0].first;
		}
		else if(V[1].size()) {
			if((V[0].size()+V[1].size())%2==0) {
				tar=V[1][0].first;
			}
			else {
				tar=V[1][0].first+1;
			}
		}
		else {
			tar=V[0][0].first;
		}
		
		
		cout<<tar<<endl;
		hoge(tar);
		
	}
}

まとめ

2D残す戦略にそこそこの時間で思いついたのは良かったね。