WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM556 Div2 Medium "XorTravelingSalesman"

問題

頂点に値がある双方向に移動できるグラフが与えられる。
現在のポイントをPとし、値Vの頂点に移動した時、
ポイントはP XOR Vになる。
例)
ポイントが5のときに値3の頂点に移動すると、
ポイントが6になる。
5(0101) XOR 3(0011) = 6(0110)

移動回数に制限はない。
また好きな時にやめる事ができ、
そのときもっていたポイントが結果となる。

最大のポイントを求めよ。

制約

1 <= 頂点の数 <= 50
0 <= 頂点の値 <= 1023

考えた事

どう手をつけていいのかわからん・・・・
とりあえず、遇数回通った頂点は反映されず、
奇数回通った頂点の値だけXORしてくわけだ
偶数回奇数回って完全にコントロールできそう?
うん。きっとできる!(直感)
ってことは、最大になるよう好きな頂点を選べるな
総当りだと2^50か・・・DP?
DPの式の立て方分からん・・・(時間切れ)
i番目の頂点までで、0~1023(0000000~1111111)を作れるか否かでいける!
Failed System Test
あ、頂点0から辿り着けない頂点抜かさなきゃ

DPって自力で式立てられた時は気持ちいいな~

ソースコード
const int MAX_N = 50;
const int MAX_V = 1023;

int N;
bool dp[MAX_N+1][MAX_V+1]; // dp[i][p] 頂点をi個使った時にポイントpはできる?
bool reach[MAX_N];         // インデックスiの頂点に頂点0から辿り着けるか  

class XorTravelingSalesman {
public:
    int maxProfit(vector <int> cityValues, vector <string> roads){
        // dpを初期化
        memset( dp, false, sizeof(dp) );
        dp[0][0] = true; // 頂点1個も使わない時はポイントは0

        // reachを初期化
        N = roads.size();
        memset( reach, false, sizeof(reach) );
        queue<int> que;
        que.push(0);
        while( !que.empty() ){
            int v = que.front(); que.pop();
            reach[v] = true;
            for( int i = 0; i < N; i++ ){
                if( roads[v][i] == 'Y' && !reach[i] ) que.push(i);
            }
        }
        
        // dpを埋めてく
        for( int i = 1; i <= N; i++ ){
            for( int v = 0; v <= MAX_V; v++ ){
                if( reach[i-1] ){
                    dp[i][v] = dp[i-1][v] || dp[i-1][v^cityValues[i-1]];
                }else{
                    dp[i][v] = dp[i-1][v];
                }
            }        
        }
        
        // できるポイントで一番大きいのを取得
        int res = 0;
        for( int v = MAX_V; v >= 0; v-- ){
            if( dp[N][v] ){
                res = v; break;
            }
        }
        return res;
    }
}