するめうめ
問題概要
原文 → 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; } };