TCO15 Round 2B med:Balance

本番は問題文が読めなくて非常にイライラした問題(多分解けなかったけど)。こんな複雑な処理みんなよく短時間で書けるなぁ。

問題

TopCoder Statistics - Problem Statement

解法

kmjpさんの解説を参考にしました。kmjp.hatenablog.jp

hashを適当に作ったからか,一つのハッシュだけで勝負すると後半の方のテストケースでWAが出ました。

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

bool used[55*55];

struct UnionFind {
    vector<int> par;
    int n, cnt;
    UnionFind(const int& x = 0) {init(x);}
    void init(const int& x) {par.assign(cnt=n=x, -1);}
    inline int find(const int& x) {return par[x] < 0 ? x : par[x] = find(par[x]);}
    inline bool same(const int& x, const int& y) {return find(x) == find(y);}
    inline bool unite(int x, int y) {
        if ((x = find(x)) == (y = find(y))) return false;
        --cnt;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    inline int count() const {return cnt;}
    inline int count(int x) {return -par[find(x)];}
};

vector<string> changeBoard(const vector<string>& board) {
    int n = board.size();
    string s;
    for (int i = 0; i < n+2; i++) s += "#";
    vector<string> ret(n+2);
    ret[0] = s;
    for (int i = 0; i < n; i++) ret[i+1] = "#" + board[i] + "#";
    ret[n+1] = s;
    return ret;
}

UnionFind uf;
map<int, int> M;

void dfs(int y, int x, const vector<string>& board, vector<vector<int> >& ret) {
    int n = board.size();
    int group = M[uf.find(y*n+x)];
    used[group] = true;
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
        if (uf.same(y*n+x, i*n+j)) {
            for (int k = 0; k < 4; k++) {
                int ny = i+dy[k];
                int nx = j+dx[k];
                if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
                int tmp = M[uf.find(ny*n+nx)];
                if (!used[tmp]) {
                    ret[group].push_back(tmp);
                    dfs(ny, nx, board, ret);
                }
            }
        }
    }
}

vector<vector<int> > createTree(const vector<string> board) {
    int n = board.size();
    uf.init(n*n);
    // unionfind木を構成する
    for (int y = 0; y < n; y++) {
        for (int x = 0; x < n; x++) {
            for (int k = 0; k < 4; k++) {
                int ny = y+dy[k];
                int nx = x+dx[k];
                if (ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
                if (board[y][x] == board[ny][nx]) {
                    uf.unite(y*n+x, ny*n+nx);
                }
            }
        }
    }
    // unionfindのサイズ
    int k = 0;
    M.clear();
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
        int tmp = uf.find(i*n+j);
        if (M.find(tmp) == M.end()) {
            M.insert(make_pair(tmp, k++));
        }
    }
    vector<vector<int> > ret(k);
    // dfsして内包関係を木グラフに落としこむ
    memset(used, false, sizeof(used));
    dfs(0, 0, board, ret);
    return ret;
}

pair<ll, ll> getHash(int cur, const vector<vector<int> > tree) {
    ll mod[2] = {1000000007, 1000000009};
    pair<ll, ll> ret = make_pair(1145141919, 5963);
    vector<pair<ll, ll> > hh;
    for (int i = 0; i < (int)tree[cur].size(); i++) {
        hh.push_back(getHash(tree[cur][i], tree));
    }
    sort(hh.begin(), hh.end());
    for (auto el : hh) {
        ret.first = ret.first*65535 + el.first;
        ret.first *= 373;
        ret.first %= mod[0];
        ret.second = ret.second*65535 + el.second;
        ret.second *= 373;
        ret.second %= mod[1];
    }
    return ret;
}

class Balance {
public:
    string canTransform(vector <string> initial, vector <string> target) {
        cout << "TEST" << endl;
        initial = changeBoard(initial);
        target = changeBoard(target);
        auto treei = createTree(initial);
        auto treet = createTree(target);
        // 木の同型性を判定する
        if (getHash(0, treei) == getHash(0, treet)) return "Possible";
        else return "Impossible";
    }
};