AtCoder ARC #211 : E - Greedy Takahashi 2

考察が結構しんどい。
https://atcoder.jp/contests/arc211/tasks/arc211_e

問題

1～Nの順列Pが与えられる。

以下の条件を満たすN点の木を成すグラフは構築できるか。
先手は、後手が以下の手順で頂点を訪問する場合、返す数列Rが辞書順最大となるように1～Nの順列Qを定める。

• 最初１番の頂点にいる。また、R=(Q[1])とする。
• 訪問済みの点に隣接する未訪問の点vのうち、Q[v]が最少となるものを選び、そこを訪問。同時に、Rの末尾にQ[v]を追加することを繰り返す。
• 最終的にR=Pとなる。

解法

P=(N,S[0],N-1,S[1],N-2,S[2],N-3,....,N-C,S[C])のような形になれば構築可能。
なお、S[n]は、再帰的に構築可能な数列を、最大値がmin(S[n-1])-1となるように全体をインクリメントしたものとする。
また、インクリメント前は辞書順でS[1],S[2],S[3]....は辞書順で降順になっていること。

再帰の際、数列をたどればCは容易に求まりS[i]の分割位置も容易に求まる。

int T,N,P[202020],re[202020];


int dfs(int L,int R,int ma) {
	if(L==R) return 1;
	vector<int> id={L};
	int i,j;
	vector<int> len;
	for(int nex=P[L]+1;nex<=ma;nex++) {
		//昇順でないといけない
		if(re[nex]<id.back()) return 0;
		if(re[nex]>=R) return 0;
		id.push_back(re[nex]);
	}
	id.push_back(R);
	int N=id.size()-1;
	pair<int,int> mal={-1,-1};
	FOR(i,N) {
		//間の数
		len.push_back(id[i+1]-id[i]-1);
		mal=max(mal,make_pair(len.back(),i));
	}
	int pre=P[L]-1;
	FOR(i,N) {
		//後ろの区間より辞書順で大きい
		if(i<N-1) {
			int larger=0;
			FOR(j,min(len[i],len[i+1])) {
				//小さいこと確定
				if(P[id[i]+j+1]-len[i]<P[id[i+1]+j+1]) return 0;
				if(P[id[i]+j+1]-len[i]>P[id[i+1]+j+1]) {
					larger=1;
					break;
				}
			}
			if(larger==0&&len[i]>len[i+1]) return 0;
		}
		//間に関係ない数字が入らない
		if(i!=mal.second) {
			for(j=id[i]+1;j<id[i+1];j++) {
				if(P[j]<pre-len[i]||P[j]>pre) return 0;
			}
		}
		//再帰
		if(dfs(id[i]+1,id[i+1],pre)==0) return 0;
		pre-=len[i];
	}
	
	return 1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) {
			cin>>P[i];
			P[i]--;
			re[P[i]]=i;
		}
		if(P[0]!=N-1) {
			cout<<"No"<<endl;
			continue;
		}
		if(dfs(1,N,N-2)) {
			cout<<"Yes"<<endl;
		}
		else {
			cout<<"No"<<endl;
		}
		
	}
}

まとめ

実装はそこまで重くないけど、考察がややこしいな…。