Maximum-Cup 2017 : G - Sparrow's trick

本番中に解ききれなかった。
https://beta.atcoder.jp/contests/maximum-cup-2018/tasks/maximum_cup_2018_g

問題

1～Nの選手が順に並んでおり、勝ち抜きトーナメント戦を行う。
選手数は2の累乗ではなく、各選手の試合数はバラバラだが、あくまで残っている選手のうち隣接する選手同士しか試合はしない。

ここで、試合結果をBNF記法に則って記述した文字列と、各選手の勝利数が与えられる。
ただし文字列は一部が欠損している。
勝利数と矛盾しない範囲で、正しい文字列を復元せよ。

解法

L～R番の選手のうち1名残るトーナメントを考えると、試合結果がどうであれ文字列数は一意に決まる。
よって(L～M)番と(M+1～R)番の選手の勝者が互いに試合する、と考えて再帰的に(L～R)番の選手のうち結果と矛盾しない構成を構築しよう。
その際、(L～R)番の中の勝者は、最終的にあと何勝するか、という状態も持って上から(1～N番から)処理するとよい。

string S,T;
string W[17];
int N;
int A[17];
vector<int> win[17],win2[17];
string ret;

int setchar(int pos,char c) {
	if(S[pos]=='?' || S[pos]==c) {
		T[pos]=c;
		return 1;
	}
	return 0;
}

int dfs(int PL,int PR,int SL,int SR,int win) {
	int tw=win+PR-PL;
	int i;
	for(i=PL;i<=PR;i++) tw-=A[i];
	if(tw) return 0;
	if(PL==PR) {
		W[PL][W[PL].size()-2]=win?'o':'x';
		FOR(i,W[PL].size()) if(setchar(SL+i,W[PL][i])==0) return 0;
		return 1;
	}
	
	if(setchar(SL,'[')==0) return 0;
	if(setchar(SL+1,'(')==0) return 0;
	if(setchar(SR,']')==0) return 0;
	if(setchar(SR-2,')')==0) return 0;
	if(setchar(SR-1,win?'o':'x')==0) return 0;
	
	
	int len=0;
	for(int PM=PL;PM<PR;PM++) {
		len+=W[PM].size();
		int tl=len+5*(PM-PL);
		
		if(dfs(PL,PM,SL+2,SL+2+tl-1,0)&&dfs(PM+1,PR,SL+2+tl,SR-3,win+1)) return 1;
		if(dfs(PL,PM,SL+2,SL+2+tl-1,win+1)&&dfs(PM+1,PR,SL+2+tl,SR-3,0)) return 1;
		
	}
	return 0;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(i=1;i<=16;i++) W[i]="[("+to_string(i)+")o]";
	
	cin>>S>>N;
	S="[("+S+")x]";
	T=S;
	vector<pair<int,int>> V;
	FOR(i,N) {
		cin>>A[i+1];
		V.push_back({i+1,A[i+1]});
	}
	
	dfs(1,N,0,S.size()-1,0);
	cout<<T.substr(2,T.size()-5)<<endl;
	
	
	
}

まとめ

本番トーナメント票を全通り列挙しようとしたらN=14あたりでTLEが生じた。