Code Formula 2014 予選B

http://code-formula-2014-qualb.contest.atcoder.jp/

ooo- で 115位です。Cでバグってかなり時間をかけてしまった。

A

irb (Rubyの対話環境) でちゃんとテストしてから出したら36秒でした。15秒で出す人の頭と手の動きはどうなっているんだろう。

puts 7-gets.to_i

B

int main(){
    string s;
    while (cin >> s){
        reverse(all(s));
        ll e = 0;
        ll o = 0;
        rep(i, s.size()){
            int d = s[i] - '0';
            if (i & 1)e += d;
            else o += d;
        }
        cout << e << " " << o << endl;
    }
}

C

6文字以下なら全探索。
そうでないなら、まず になっている箇所を取り除く。このときの長さが7以上なら目標は達成できないのは明らかで、6以下なら適当に等しい箇所の文字を付け足して6文字にする。その後に全探索。

アルゴリズム自体はすぐに思いついたが全探索のところで変なバグを埋め込み、1時間近く悩んでしまい上の順位になった。予選通過は恐らく無理。

デバッグ中に になっているケースを見つけたのでclarを投げた。

string a, b;
int n;
bool solve(){
    if (n <= 6){
        set<string> S;
        S.insert(a);
        rep(k, 3){
            set<string> T;
            for (string x : S){
                rep(i, n)loop(j, i + 1, n){
                    string s = x;
                    swap(s[i], s[j]);
                    T.insert(s);
                }
            }
            swap(S, T);
        }
        return S.count(b);
    }
    vi diff, same;
    rep(i, n){
        if (a[i] != b[i]) diff.push_back(i);
        else same.push_back(i);
    }

    string na, nb;
    int d = diff.size();
    if (d >= 7) return false;

    rep(i, d){
        na.push_back(a[diff[i]]);
        nb.push_back(b[diff[i]]);
    }
    rep(i, same.size()){
        if (na.size() >= 6) break;
        na.push_back(a[same[i]]);
        nb.push_back(b[same[i]]);
    }

    set<string> S;
    S.insert(na);
    rep(k, 3){
        set<string> T;
        for (string s : S){
            rep(i, s.size())loop(j, i + 1, s.size()){
                swap(s[i], s[j]);
                T.insert(s);
            }
        }
        swap(S, T);
    }
    return S.count(nb);
}

int main(){
    while (cin >> a >> b){
        n = a.size();
        if (a.size() == 1) throw;
        cout << (solve() ? "YES" : "NO") << endl;
    }
}