TopCoder SRM 719 Div2 Hard:TwoDogsOnATree

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

頂点からなる木が与えられる。辺 にはそれぞれ重み が設定されており、パス のコストは、 と の間にある辺の重みの XOR と定義する。

与えられた木から、辺の重複が無いようにパスを つ選ぶとき、 つのパスのコストの XOR の最大値を求めよ。

解説

思いつかなくて解説を読んだのですが、想定解法が頭良すぎて感動しました。

パス のコストは、通常なら と と に分解して・・・とやると思いますが、今回の問題で定義されているパスのコストは XOR ですので、 は偶数回通って打ち消されるため、 と の XOR を取るだけで求められます。よって、 という値を求めておくことで、パス のコストは のように で求めることができます。

あとは、「辺の重複を許さずに」パスを つ選ぶというところが厄介に感じますが、実はそれほど厄介ではありません。

重複を気にせずにパスを と の つ選んだとします。 つのパスの XOR は、当然 となります。重複がなければこれで良いですが、ある場合はどうすれば良いでしょうか？これはパスを入れ替えることで解決できます。つまり、 と に変える、または と に変えることで、重複のない形に変更できます。この場合のコストもやはり先ほどと同じように計算できます。

これにより、重複を許して の値を つ選んだときの XOR の最大値を求める問題に帰着できました。ここまで来ればあとは簡単で、全探索や DP をやれば良いです。

ソースコード

class TwoDogsOnATree {
    public:
    int X[1010], can[1024];
    int maximalXorSum(vector<int> parent, vector<int> w) {
        memset(X, 0, sizeof(X));
        memset(can, false, sizeof(can));
        int N = parent.size();
        for(int i=0; i<N; i++) {
            X[i+1] = X[parent[i]] ^ w[i];
        }

        N++;
        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                can[ X[i] ^ X[j] ] = true;
            }
        }

        int ans = 0;
        for(int i=0; i<1024; i++) {
            for(int j=0; j<1024; j++) {
                if(can[i] && can[j]) chmax(ans, i^j);
            }
        }
        return ans;
    }
};