Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2009-01-19

GroupedWord (SRM432 DIV1 Medium)

| 00:27 | GroupedWord (SRM432 DIV1 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - GroupedWord (SRM432 DIV1 Medium) - TopCoder煮ブログ

泥臭い方法しか思いつかなかったので泥臭く解いた。単語ごとに含まれる文字と先頭・末尾の文字を記憶しておく。

struct WORD{
    int flag;   // 含まれる文字
    int s;      // 先頭の文字
    int e;      // 末尾の文字
    string str; // 文字列全体
};

parts として与えられたものを WORD に変換して、適宜結合していきつつ、最終的に2つ以上残れば MANY、1つなら str を返すようにする。

Test case は全部通ったので、Submit したら System Test Failed。aab, bbb, bc のときに、aab と bc を先に結合していたので、aabc と bbb を IMPOSSIBLE と判断してしまっていた。ロジックをちょっと修正して、同じ文字だけで構成される part を最初に結合していくようにしたら通った。

C++ 一位の人の解も同じ感じの解き方のようだ。join1 で bbb を先に結合して、その後に通常の結合を実施していた。よく思いつくなぁ。

以下、自分の解。恥ずかしいぐらいに長い。

#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <sstream>
#include <algorithm>
#include <set>
#include <numeric>
using namespace std;

struct WORD{
    int flag;
    int s;
    int e;
    string str;
};

class GroupedWord {
public:
    WORD parseWord(string s){
        WORD w;
        w.str = "";

        w.flag = 0;
        char c = 0;
        for(int i = 0; i < s.size(); i++){
            if(c == s[i]) continue;
            c = s[i];
            int cf = 1 << (c - 'a');
            if(w.flag & cf) return w;
            w.flag += cf;
        }
        w.s = 1 << (s[0] - 'a');
        w.e = 1 << (s[s.size() - 1] - 'a');
        w.str = s;

        return w;
    }

    string restore(vector <string> parts) {
        int N = parts.size();
        vector<WORD> words(N);
        for(int i = 0; i < N; i++){
            words[i] = parseWord(parts[i]);
            if(words[i].str == "") return "IMPOSSIBLE";
        }
        for(int i = N - 1; i >= 0; i--){
            if(words[i].s == words[i].e){
                for(int j = 0; j < words.size(); j++){
                    if(i != j){
                        if(words[i].s == words[j].s){
                            words[j].str = words[i].str + words[j].str;
                            words.erase(words.begin() + i);
                            break;
                        }else if(words[i].s == words[j].e){
                            words[j].str += words[i].str;
                            words.erase(words.begin() + i);
                            break;
                        }
                    }
                }
            }
        }

        for(int i = 0; i < words.size() - 1; i++){
            for(int j = i + 1; j < words.size(); j++){
                int dup = words[i].flag & words[j].flag;
                if(dup == 0) continue;
                if(__builtin_popcount(dup) > 1) return "IMPOSSIBLE";

                WORD w;
                if(dup & words[i].s && dup & words[j].e){
                    w = parseWord(words[j].str + words[i].str);
                }else if(dup & words[j].s && dup & words[i].e){
                    w = parseWord(words[i].str + words[j].str);
                }else{
                    return "IMPOSSIBLE";
                }

                words.erase(words.begin() + j);
                words.erase(words.begin() + i);
                words.push_back(w);
                i = -1;
                break;
            }
        }

        return words.size() == 1 ? words[0].str : "MANY";
    }
}