Distributed Code Jam 2016 Round 1 : C. rps

またジャンケン。
https://code.google.com/codejam/contest/11264486/dashboard#s=p2

問題

N人からなるトーナメント表に基づいて試合を行い、優勝者を決めたい。
各人は、決められたジャンケンの手を出し続ける。
同じ手を出す人同士の対戦では、表中で先にいる人が勝利となる。

最終的な勝者は表中何番目の人か答えよ。

解法

ノードは最大100である。
トーナメント表を64ブロックに分割して、各ノードでブロック毎の優勝者を求め、最後にマスターノードで各ブロックの優勝者同士のトーナメント戦を行えばよい。

int TN,MY;
ll N;
const int D=6;

int winright(char a,char b) {
	if(a==b) return 0;
	if(a=='R' && b=='S') return 0;
	if(a=='S' && b=='P') return 0;
	if(a=='P' && b=='R') return 0;
	return 1;
}

vector<pair<int,char>> go(vector<pair<int,char>> V) {
	int i;
	while(V.size()>1) {
		vector<pair<int,char>> VV;
		FOR(i,V.size()/2) VV.push_back(V[i*2+winright(V[i*2].second,V[i*2+1].second)]);
		swap(V,VV);
	}
	return V;
}

void solve(){
	int i,j,k,l,r,x,y; string s;
	vector<pair<int,char>> V;
	N=GetN();
	if(N<=D) {
		if(MY!=0) return;
		FOR(i,1<<N) V.push_back({i,GetFavoriteMove(i)});
		
		V=go(V);
		cout<<V[0].first<<endl;
	}
	else {
		if(MY>=1<<D) return;
		FOR(i,1<<(N-D)) V.push_back({(MY<<(N-D)) + i,GetFavoriteMove((MY<<(N-D)) + i)});
		
		V=go(V);
		PutInt(0,V[0].first);
		PutInt(0,V[0].second);
		Send(0);
		
		if(MY==0) {
			for(i=1;i<1<<D;i++) {
				Receive(i);
				x=GetInt(i);
				y=GetInt(i);
				V.push_back({x,y});
			}
			V=go(V);
			cout<<V[0].first<<endl;
		}
		
	}
}

まとめ

昨年のRound1よりは簡単だね。GCJ Round2参加者向け相当だからかな。