hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

TopCoder SRM 719 Div2 Hard:TwoDogsOnATree

するめうめ

tsutaj.hatenablog.com

問題概要

原文 → TopCoder Statistics - Problem Statement

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

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

解説

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

パス  (a, b) のコストは、通常なら  ( \mathrm{root}, \mathrm{lca}(a, b) ) ( \mathrm{root}, a ) ( \mathrm{root}, b ) に分解して・・・とやると思いますが、今回の問題で定義されているパスのコストは XOR ですので、  ( \mathrm{root}, \mathrm{lca}(a, b) ) は偶数回通って打ち消されるため、  (\mathrm{root}, a) (\mathrm{root}, b) の XOR を取るだけで求められます。よって、  X_{i} = \mathrm{cost} (\mathrm{root}, i) という値を求めておくことで、パス  (a, b) のコストは  X_{a} \ \  \mathrm{XOR} \ \  X_{b} のように  O(1) で求めることができます。

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

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

これにより、重複を許して  X_{i} の値を  4 つ選んだときの 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;
    }
};