Google Code Jam 2016 Round 2 : A. Rather Perplexing Showdown

本番非常にドタバタしたが、土壇場でB-largeを通して何とかRound3進出権を得た。
https://code.google.com/codejam/contest/10224486/dashboard#s=p0

問題

計2^N人でジャンケントーナメントを行う。
各人はトーナメント中常に同じ手しか出さない。

グーチョキパーを固定で出す人数が決められている。
途中であいこを出さず単一の優勝者が出せるトーナメントを構築できるか。
出来るなら、トーナメントの並び順をグーチョキパーを出す人に対しR,P,Sで表記して連結してできる文字列のうち、辞書順最小なものを求めよ。

解法

試合の勝者の手を決めると、試合前の２人の手は一意に決まる。
よってグー・チョキ・パーを優勝者とするN回戦まであるトーナメントをそれぞれ考えると、並び順はともかく組み合わせは一意に決まる。

そこでまずは３通りの優勝パターンの組み合わせを作ってみよう。
うち入力とトーナメント中の人数が一致するものがあれば、それを答える。

辞書順最小の処理については、トーナメントを構成する木に対し葉から順に文字列を作っていき、各頂点では両子頂点に対応する文字列のうち小さい方を前に持ってくる、という手順を根まで繰り返せばよい。
以下のコードは、先に文字列を生成し、２分割して前後並べ替えるということを再帰的に行うことで代替している。

int N,R,P,S;
vector<int> memo[5][50];

vector<int> win(int cur,int level) {
	vector<int>& v= memo[cur][level];
	if(v.empty()) {
		if(level==0) {
			v.push_back(cur);
		}
		else {
			vector<int> a,b;
			if(cur==0) a=win(0,level-1),b=win(1,level-1);
			if(cur==1) a=win(1,level-1),b=win(2,level-1);
			if(cur==2) a=win(2,level-1),b=win(0,level-1);
			FORR(r,a) v.push_back(r);
			FORR(r,b) v.push_back(r);
		}
	}
	return v;
}
string sortsort(string S) {
	if(S.size()==1) return S;
	
	string a=sortsort(S.substr(0,S.size()/2));
	string b=sortsort(S.substr(S.size()/2));
	return min(a,b)+max(a,b);
	
}

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	char SS[4]="PRS";
	cin>>N>>R>>P>>S;
	
	vector<int> V[3];
	V[0]=win(0,N);
	V[1]=win(1,N);
	V[2]=win(2,N);
	string Ret="";
	FOR(i,3) {
		int num[3]={};
		FORR(r,V[i]) num[r]++;
		if(num[0]!=P) continue;
		if(num[1]!=R) continue;
		if(num[2]!=S) continue;
		string s;
		FORR(r,V[i]) s+=SS[r];
		s=sortsort(s);
		if(Ret.empty() || s<Ret) Ret=s;
	}
	
	
	if(Ret.empty()) {
		_P("Case #%d: IMPOSSIBLE\n",_loop);
	}
	else {
		_P("Case #%d: %s\n",_loop,Ret.c_str());
	}
}

まとめ

これは割と面白かった。