はまやんはまやんはまやん

hamayanhamayan's blog

Tr/ee [AtCoder Regular Contest 103 E]

https://beta.atcoder.jp/contests/arc103/tasks/arc103_c

考察過程

1. 実験してみると、作れる最低条件が3つ見つかる
2. 「S[0]は1」「S[N-1]は0」「Sの[0,N-2]は回分になっている」
3. これ以外なら作れると仮定して考える
4. 1なら普通に辺を伸ばせば大丈夫
5. 0なら分岐させる必要がある
6. これで全部作れそう?

解法

https://beta.atcoder.jp/contests/arc103/submissions/3309244

「S[0]は1」「S[N-1]は0」「Sの[0,N-2]は回分になっている」場合に構築ができる。
なので、以上の条件を満たさない場合は-1として答えよう。
 
先頭N-1個の文字を見て、
1なら「辺を伸ばして先頭を移動させる」、
0なら「今の頂点にくっつける形で辺を伸ばして先頭はそのまま」
という方針で辺を張っていく。

これだけでAC

string S;
int N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S;
    N = S.length();
 
    if (S.front() == '0' or S.back() == '1') {
        printf("-1\n");
        return;
    }
 
    rep(i, 0, (N - 1) / 2) if (S[i] != S[N - 2 - i]) {
        printf("-1\n");
        return;
    }
 
    vector<pair<int, int>> ans;
    int top = 0;
    rep(i, 0, N - 1) {
        ans.push_back({ top, i + 1 });
 
        if (S[i] == '1') top = i + 1;
    }
 
    fore(p, ans) printf("%d %d\n", p.first + 1, p.second + 1);
}