読者です 読者をやめる 読者になる 読者になる

JAG模擬国内2016 C-みさわさんの根付き木

http://jag2016-domestic.contest.atcoder.jp/tasks/jag2016secretspring_c
ああ無情。
 なんだか妙なフォーマットで与えられる根付き木をマージしろという問題。
 これはいわゆる構文解析と呼ばれる問題らしいですがそんなこと知らないのでいつものように思考停止深さ優先探索で解きました。たしか40分くらいで書けたんですけど2ケースだけバグって全然WAが取れなかったのですが、さきほど公開されたテストケースを手元で試したらバグが判明。なんと自作のint_to_string関数で引数が0のときstring res = "" が返ってくる仕様になっていたのでした……。とほほ……。しかも

char zero = '0'

とか書いてあってこれもう例外処理する気満々じゃないですか。なんで書き忘れるかなあ……。

typedef pair<int, int> pint;
const pint gomi = pint(-1, -1);
string s1, s2;
int st_to_int(string s){
    int n = s.size();
    int res = 0;
    int keta = 1;
    for(int i = n - 1; i >= 0; --i){
        res += (s[i] - '0') * keta;
        keta *= 10;
    }
    return res;
}
pint find_ne(const string& s, pint it){
    int height = 0;
    string temp = ""; 
    REP(i, it.first, it.second){
        char a = s[i];
        if(a == '('){
            height ++;
        }else if(a == ')'){
            height--;
        }else if(a == '['){
            continue;
        }else if(a == ']'){
            if(height == 0) return pint(st_to_int(temp), i);
            temp = "";
        }else{
            temp += a;
        }
    }
    return gomi;
}
string int_to_string(int k){
    string res = "";
    char zero = '0';
    if(k == 0) res += zero;
    for(; k > 0;){
        char a = zero + (k % 10);
        res = a + res;
        k /= 10;
    }
    return res;
}
string search(pint s1_it, pint s2_it){
    string res = "";
    pint v = find_ne(s1, s1_it), w = find_ne(s2, s2_it);
    if(v != gomi && w != gomi){
        string k = int_to_string(v.first + w.first);
        string a = search(pint(s1_it.first + 1, v.second - 3), pint(s2_it.first + 1, w.second - 3));
        string b = search(pint(v.second + 2, s1_it.second - 1), pint(w.second + 2, s2_it.second - 1));
        res += "(" + a +  ")[" + k + "](" + b + ")";
    }
    return res;
}
int main(){
    cin >> s1 >> s2;
    cout << search(pint(0, s1.size()), pint(0, s2.size())) << endl;
    return 0;
}

見るからにバグりそうなコードなので普通に解法がバグってるのかと思いましたよ……。ああつらい。
 根を探す→両側の文字列の両端の(と)を取り除いて根を探す、という操作をしてるんですが、イテレーションが少し面倒ですね。でも二分木のライブラリなんて持ってないので仕方ないですね。
 それにしても最近何のコンテストに出てもバグを埋めてばかりでつらいです。
 今日の夜中初めてcodeforcesに出たのですがTopcoderと比べるとかなり実装寄りでびっくりしました。バグの嵐でDiv1に上がれず。つらい。前日にするめ開始四分前にログインしたらregister出来なかったのもつらかったですが……。五分前ルールなんて知りません。
 なんか情弱過ぎて生きるのがつらいですね……(完)。