Google Code Jam 2019 Round 1C : A. Robot Programming Strategy

1A,1Bよりはわかりやすい。
https://codingcompetitions.withgoogle.com/codejam/round/00000000000516b9/0000000000134c90

問題

2^K人でトーナメントを行う。
各トーナメントではじゃんけんで勝負を決める。
互いに出す手は決まっており、1回でも先に買った方が勝者となる。

自分以外の(2^K-1)人の手がわかっているとき、トーナメントの対戦順がどうであっても自分が優勝する手順は存在するか。
存在するなら一例を示せ。

解法

どんなトーナメントでも優勝するには、だれと初戦で当たるかわからないので結局全員に勝てなければいけない。
よって全員に勝てる手順を求めよう。
まず全員の手順を500文字以上に複製しておこう。

対戦相手を手順の順でソートしておく。
まず1手目に3通りすべてが登場する場合、何を出しても勝てない相手がいるので全員に勝つのは無理。
1通りなら全員に勝てる。2通りなら、片方は勝ち、片方はあいこに持ち込める。
あいこに持ち込んだ場合、あいこになった相手に対し、今度は2手目に何通り登場するか…と順に見ていく。

事前に手順の順でソートしておくと、あいこになる相手は常に区間となるので管理が容易。

int T;
int N;
string ST[505];

string hoge(int p,int PL,int PR) {
	if(PR<=PL) return "";
	int R=0,P=0,S=0;
	int LP=505,RP=-1,LR=505,RR=-1,LS=505,RS=-1;
	int i;
	for(i=PL;i<PR;i++) {
		if(ST[i][p]=='P') P++, LP=min(LP,i), RP=max(RP,i+1);
		if(ST[i][p]=='R') R++, LR=min(LR,i), RR=max(RR,i+1);
		if(ST[i][p]=='S') S++, LS=min(LS,i), RS=max(RS,i+1);
	}
	if(P&&R&&S) return "IMPOSSIBLE";
	if(P&&!R&&!S) return "S";
	if(!P&&R&&!S) return "P";
	if(!P&&!R&&S) return "R";
	
	if(P&&R&&!S) {
		string s=hoge(p+1,LP,RP);
		if(s=="IMPOSSIBLE") return s;
		return "P"+s;
	}
	if(P&&!R&&S) {
		string s=hoge(p+1,LS,RS);
		if(s=="IMPOSSIBLE") return s;
		return "S"+s;
	}
	if(!P&&R&&S) {
		string s=hoge(p+1,LR,RR);
		if(s=="IMPOSSIBLE") return s;
		return "R"+s;
	}
	
	return "";
}

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) {
		cin>>ST[i];
		while(ST[i].size()<500) ST[i]+=ST[i];
	}
	sort(ST,ST+N);
	string ret=hoge(0,0,N);
	
	_P("Case #%d: %s\n",_loop,ret.c_str());
}

まとめ

トーナメント云々の設定、考察には若干影響するけど実装には関係ないし、無くてもよかったんでは…。