ARC 103 E - Tr/ee - ykmakuのブログ

問題

解法

木という条件から、 $s_1 = 1, \ s_n = 0, \ s_i = s_{n-i}$ でないといけない事がわかります。
逆にこの条件が成り立っているとき条件を満たす木を構成できます。
まず $(1,2)$ という枝を用意します。 $now=2$ とします。 $s$ の2文字目から見ていき、 $i$ 番目の文字を見ているとき枝 $(now,i+1)$ を追加します。 $s_i=1$ なら $now=i+1$ とします。
イメージとしては作りたい木をイモムシだと思ったときに $s_i=1$ ならイモムシの体をのばして、そうでないなら体の先端に足をはやす、という感じでしょうか。（英語版解説にあるcaterpillarは毛虫という意味だそうです。）

感想

コンテスト中にこの問題を通せたので嬉しかった。

#include <iostream>
#include <string>
#include <vector>

using namespace std;

typedef pair<int,int> P;

int main()
{
  string s;
  cin >> s;
  int n = s.size();

  if(s[0] == '0' || s[n-1] == '1'){
    cout << -1 << endl;
    return 0;
  }

  s = s[n-1] + s;

  for(int i = 0; i <= n; i++){
    if(s[i] != s[n-i]){
      cout << -1 << endl;
      return 0;
    }
  }

  int now = 2;
  vector<P> ans;
  ans.push_back(P(1,2));
  for(int i = 2; i < n; i++){
    if(s[i] == '0'){
      ans.push_back(P(now,i+1));
    }else{
      ans.push_back(P(now,i+1));
      now = i+1;
    }
  }

  for(int i = 0; i < ans.size(); i++){
    cout << ans[i].first << " " << ans[i].second << endl;
  }

  return 0;
}