AtCoder ARC #103 : E - Tr/ee

こういうの苦手。
https://beta.atcoder.jp/contests/arc103/tasks/arc103_c

問題

N文字の0/1からなる文字列が与えられる。
以下を満たす木を成すN頂点のグラフを構築可能か。可能なら構築せよ。

• 1辺を取り除いて木を二つの連結成分に分割するとき：
  • S[i]==0なら頂点数iとなる連結成分はどうやっても作れない。
  • S[i]==1なら頂点数iとなる連結成分が作れる辺がある。

解法

まず以下の自明なことを確認しよう。

• 葉からつながる辺を考えると、S[1]==1でなければならない。
• 辺を１つは切らないといけないので、S[N]===0でなければならない。
• ２つの連結成分を作ることを考えると、S[i]==S[N-i]でなければならない。

これらをすべて満たす場合、条件を満たす木が構築可能である。
Nを根とする1～Nのラベル付き木を考える。ここで仮にS[N]=1としておく。
(N-1)～1の順で、親頂点を探していこう。

今考えている頂点iに対し、すでにある木にある頂点jのうち、S[j]=1となる最小のjを考える。
ラベルの大きい順に頂点を追加しているので、jはiより大きい。
その場合iをjにつなごう。

そうすると以下の通り条件を満たす木が作れる。

• S[j]==1のとき、i＜jとなる頂点はすべてjのSubTree内に来るので、このSubTreeの大きさはjとなり、条件を満たす。
• S[j]==0のとき、jは葉になるのでSubTreeの大きさは1である。S[1]=1は検証済みなので問題ない。また、大きさjのSubTreeが構築されることはない。

int N;
string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	N=S.size();
	if(S[N-1]=='1') return _P("-1\n");
	if(S[0]=='0') return _P("-1\n");
	for(i=1;i<=N-1;i++) if(S[i-1]!=S[N-1-i]) return _P("-1\n");
	S[N-1]='1';
	
	int pre=N;
	for(i=N-1;i>=1;i--) {
		cout<<i<<" "<<pre<<endl;
		if(S[i-1]=='1') pre=i;
	}
	
}

まとめ

こういうのどうすれば得意になるんだろうな。