ARC103 E - Tr/ee

問題

長さnの文字列sが与えられる
以下の条件を満たすn頂点の木が存在するか判定し、存在する場合は具体的に1つ構築せよ

(条件)
1-basedで、
s[i]= '1' のとき) 木からある辺を1つ取り除くことでサイズiの連結成分が作れる
s[i]= '0' のとき) 木からどのように辺を1つ取り除いてもサイズiの連結成分が作れない

2 <= n <= 10^5

解法

頂点数2以上の木には葉が最低2つはあるから、s[1]は1である必要がある
またサンプル1の通り、n頂点の木から辺を1本取り除いてできる連結成分のサイズは絶対n未満だから、s[n]は0である必要がある
更に、ある辺を取り除いてサイズiの連結成分が作れるとき、もう片方の連結成分のサイズはn-iになるから、s[i]=s[n-i]が任意のiについて成り立つ必要もある

これらさえ満たせばどんなsが与えられても条件を満たすような木が作れる
例えば
i=n-1から始めて1減らしながら見ていき、i＜jかつs[j]=1であるようなjの最小値(存在しなければn)をiの親として辺で結ぶ
これを繰り返せば作れる
↓具体例

int n;
string s;

int main() {
	cin >> s;
	n = s.size();
	if (s[0]=='0' || s[n-1]=='1') return cout << -1 << endl, 0;
	for(int i=1; i<n-1; i++) if (s[i-1]!=s[n-i-1]) return cout << -1 << endl, 0;
	int p = n;
	for (int i=n-1; i>=1; i--) {
		cout << i << ' ' << p << endl;
		if (s[i-1]=='1') p = i;
	}
}

木が作れるための条件と、その条件さえ満たせば何でも作れそうだなって推測は5分で立ったんだけど、具体的にどういう風に木を作ればいいのか思いつくまで1時間もかかった
俺はその間何をやってたんだろう？
木→根付き木→部分木とか木に関連するワードはそんなに多くないしその辺をベースにしていろいろ実験すれば絶対1時間もかからなそうなのに
第一に、最近めっちゃ早寝早起きしてるせいでコンテスト開始時点でめちゃくちゃ眠かったのも要因だと思う
眠いと考察を進めるスピードがかなり落ちる
あとは単純に俺が構築系の問題が苦手なことに気付いた
今まで構築問題が出たときは大体同じ点数の構築じゃない問題と比べてやたら時間がかかってる or コンテスト時間内に解けてない
これはどうすれば改善できるんだろう？
他のジャンルなら類題をいっぱい解けば良いけど構築問題をいっぱい解いたところで応用がきくのか？
試しにググったところ、データ構造を勉強した結果若干構築が得意になったという人を見つけた
言われてみれば俺は遅延なしセグ木すら完璧に理解してないくらいデータ構造に弱い
特定のデータ構造を知らないと絶対解けないような問題にあんまり遭遇しないから後回しにしがちだった
どれくらい改善されるかはわからないけど、今後はデータ構造をちょっとずつ勉強してみたいと思う
競プロ以外でもどっかで活きることを期待しつつ・・