Hatena::Grouptopcoder

hasiの日記

 | 

2010-11-11

Marathon Match 66 - DigitsPattern

18:14

たまには最終テスト前に。

問題

http://www.topcoder.com/longcontest/?module=ViewProblemStatement&rd=14412&pm=11123

手法

たぶんd:id:komiyam:20101110:1289412487と同じ。でもこっちのほうがちょっと速そう。6*7のケースがローカルで2秒ぐらい。でもメモ化とかはしてない。

(追記:辺の向きが逆になってて得意苦手が逆転しているらしい)

アルゴリズムJavaScript可視化してみた。確認用に作った。

http://imoz.jp/temp/mm/mm66.html (chromefirefoxでテスト)

ソース

#include <cstdlib>
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <stack>
#include <algorithm>

using namespace std;

typedef pair<int,int> pairint;
#define mp make_pair

const int di[4] = {+1, 0,-1, 0};
const int dj[4] = { 0,+1, 0,-1};

int H, W;
int tar[128][128];
bool unv[128][128];
bool vis[128][128];
vector<pairint> result;
typedef map<pairint, vector<pairint> > P_t;
P_t P;

class DigitsPattern {
public:
    void visit(pairint n) {
        if (vis[n.first][n.second]) return;
        vis[n.first][n.second] = true;
        const vector<pairint>& a = P.find(n)->second;
        for (unsigned i = 0; i < a.size(); ++ i) {
            visit(a[i]);
        }
        result.push_back(n);
    }

    int func(vector<pairint>& Q, P_t& parents) {
        vector<pairint> R;
        int score = 0;
        for (;;) {
            for (unsigned p = 0; p < Q.size(); ++ p) {
                int i = Q[p].first;
                int j = Q[p].second;
                int n = 0;
                for (int k = 0; k < 4; ++ k) {
                    if (unv[ i+di[k] ][ j+dj[k] ]) ++ n;
                }
                if (n == 0) {
                    score += abs(tar[i][j]);
                    unv[i][j] = false;
                } else if (tar[i][j] <= 0) {
                    unv[i][j] = false;
                    score += -tar[i][j];
                    for (int k = 0; k < 4; ++ k) {
                        if (unv[ i+di[k] ][ j+dj[k] ]) {
                            -- tar[ i+di[k] ][ j+dj[k] ];
                            parents[Q[p]].push_back(mp(i+di[k], j+dj[k]));
                        }
                    }
                } else if (tar[i][j] >= n) {
                    unv[i][j] = false;
                    score += tar[i][j] - n;
                    for (int k = 0; k < 4; ++ k) {
                        if (unv[ i+di[k] ][ j+dj[k] ]) {
                            parents[mp(i+di[k], j+dj[k])].push_back(Q[p]);
                        }
                    }
                } else {
                    R.push_back(Q[p]);
                }
            }
            if (Q.size() == R.size()) break;
            Q.swap(R);
            R.clear();
        }
        if (Q.size() != 0) {
            vector< vector<pairint> > clus;
            for (unsigned p = 0; p < Q.size(); ++ p) {
                int i = Q[p].first;
                int j = Q[p].second;
                if (unv[i][j]) {
                    vector<pairint> a;
                    stack<pairint> S;
                    S.push(Q[p]);
                    unv[i][j] = false;
                    while (!S.empty()) {
                        pairint t = S.top();
                        S.pop();
                        a.push_back(t);
                        for (int k = 0; k < 4; ++ k) {
                            pairint s(t.first + di[k], t.second + dj[k]);
                            if (unv[s.first][s.second]) {
                                S.push(s);
                                unv[s.first][s.second] = false;
                            }
                        }
                    }
                    clus.push_back(a);
                }
            }
            for (unsigned p = 0; p < clus.size(); ++ p) {
                score += select(clus[p], parents);
            }
        }
        return score;
    }

    int select(const vector<pairint>& Q, P_t& parents) {
        P_t par0;
        vector<int> tartmp(Q.size());
        for (unsigned p = 0; p < Q.size(); ++ p) {
            int i = Q[p].first;
            int j = Q[p].second;
            tartmp[p] = tar[i][j];
            par0.insert(mp(Q[p], vector<pairint>()));
        }
        int best = 1<<30;
        P_t B;
        for (unsigned p = 0; p < Q.size(); ++ p) {
            for (unsigned q = 0; q < Q.size(); ++ q) {
                int i = Q[q].first;
                int j = Q[q].second;
                unv[i][j] = (p != q);
            }
            int i = Q[p].first;
            int j = Q[p].second;
            P_t par = par0;
            int n = 0;
            for (int k = 0; k < 4; ++ k) {
                if (unv[ i+di[k] ][ j+dj[k] ]) {
                    ++ n;
                    par[mp(i+di[k], j+dj[k])].push_back(Q[p]);
                }
            }
            vector<pairint> QQ = Q;
            QQ.erase(QQ.begin() + p);
            int score = func(QQ, par) + (n - tar[i][j]);
            if (score < best) {
                best = score;
                B = par;
            }
            for (unsigned q = 0; q < Q.size(); ++ q) {
                int i = Q[q].first;
                int j = Q[q].second;
                tar[i][j] = tartmp[q];
            }
            unv[i][j] = true;
        }
        for (P_t::const_iterator i = B.begin(); i != B.end(); ++ i) {
            for (unsigned j = 0; j < i->second.size(); ++ j) {
                parents[i->first].push_back(i->second[j]);
            }
        }
        for (unsigned q = 0; q < Q.size(); ++ q) {
            int i = Q[q].first;
            int j = Q[q].second;
            unv[i][j] = true;
        }
        return best;
    }

    vector <int> recreate(vector <string> targetPattern) {
        H = targetPattern.size();
        W = targetPattern[0].size();
        vector<pairint> Q;
        for (int i = 0; i < H; ++ i) {
            for (int j = 0; j < W; ++ j) {
                if (targetPattern[i][j] != '.') {
                    tar[i+1][j+1] = targetPattern[i][j]-'1';
                    unv[i+1][j+1] = true;
                    Q.push_back(mp(i+1, j+1));
                    P.insert(mp(mp(i+1, j+1), vector<pairint>()));
                }
            }
        }
        func(Q, P);
        for (P_t::const_iterator i = P.begin(); i != P.end(); ++ i) {
            visit(i->first);
        }
        vector<int> r(result.size()*2);
        for (unsigned i = 0; i < result.size(); ++ i) {
            r[2*i]   = result[i].first-1;
            r[2*i+1] = result[i].second-1;
        }
        return r;
    }
};
 |