2016 TCO Algorithm Round 1A hard: EllysTree

問題

TopCoder Statistics - Problem Statement

解法

まず最初に, 「ある頂点からはどの頂点に行けるか」というのを dfs してメモっておきます。

この問題は実は貪欲に解けます。すなわち, 「now = 0 からスタートし, now -> next と移動してもすべての頂点を移動しきれるならなるべく小さい next を選ぶ」という戦略で解けます。
これは, 「now -> next と移動してもすべての頂点を移動しきれるか」の判定関数がどうなるのかを考えるとわかります。

判定関数の準備として, ord という配列を用意しておきます。これは 0, 1, ..., n-1 の順列になっていて, 頂点 v が葉に近いほど v は前の方に来るようにします。

すると, check(now, v) = (今頂点 now にいて, 既に訪れた頂点の状況が配列 v で表されるときにすべての頂点にたどり着けるか) というのは, ord が前の方にある頂点を優先しながら移動してすべての頂点を訪れることができたら true, 失敗したら false, で判定できます。

この様に 「葉が近いもの優先で頂点を訪れる」というのがすべての頂点を通ることに関して最適な戦略である理由は, 葉側の頂点は自由度が低く, その先祖の方が自由度が高い, というのが理由です。葉側の頂点 v とそれより先祖の頂点 u について, 先に v におとずれておくと, v 以前の分岐にもいけますが, 先に u におとずれてから v に行くと, v 以前の分岐に戻れない可能性があります。先に v におとずれて損をすることはないので, なるべく葉側から通るのが良いです。

bool can[101][101], vis[101];
vector<int> T[101];
int n;

void dfs(int v, vi& ord) {
    vis[v] = true;
    for (int i = 0; i < n; i++) if (vis[i]) {
        can[v][i] = can[i][v] = true;
    }
    for (int u : T[v]) if (!vis[u]) {
        dfs(u, ord);
    }
    ord.push_back(v);
    vis[v] = false;
}

bool check(int now, const vi& v, const vi& ord) {
    vi w = v;
    int cnt = 0;
    for (int el : w) cnt += el;
    while (cnt < n) {
        bool ng = true;
        for (int el : ord) {
            if (can[now][el] && !w[el]) {
                now = el;
                ng = false;
                w[now] = 1;
                break;
            }
        }
        if (ng) return false;
        cnt++;
    }
    return true;
}

class EllysTree {
public:
    vector <int> getMoves(vector <int> parent) {
        n = parent.size() + 1;
        for (int i = 0; i < n; i++) T[i].clear();
        for (int i = 1; i < n; i++) {
            T[i].push_back(parent[i-1]);
            T[parent[i-1]].push_back(i);
        }
        vector<int> ord;
        memset(can, false, sizeof(can));
        memset(vis, false, sizeof(vis));
        dfs(0, ord);
        vi ans, v(n);
        v[0] = 1;
        if (!check(0, v, ord)) return ans;
        int cnt = 1, now = 0;
        while (cnt < n) {
            for (int i = 0; i < n; i++) if (!v[i] && can[now][i]) {
                v[i] = 1;
                if (check(i, v, ord)) {
                    now = i;
                    cnt++;
                    break;
                } else v[i] = 0;
            }
            ans.push_back(now);
        }
        return ans;
    }
};