TopCoder SRM 556 Div1 Easy XorTravelingSalesman

SRM556は不参加だけど復習。
http://community.topcoder.com/stat?c=problem_statement&pm=12175

50個までの頂点からなるグラフにおいて、辺の有無と、各点のスコアが与えられる。
点0からスタートして、各点を複数回通ってもいいので、点のスコアをXorで累積していく場合の最大値を求める。

この問題、スコアは1023までなので、Xorの範囲は0～1023。
なので、各頂点で0～1023までのスコアをとりうるかを配列で覚えておく。
あとはDPで各頂点のスコアから隣接点のスコアを更新するのを繰り返す。
点は50個なので、せいぜい計算は50x50x1024回で計算量も問題なし。

class XorTravelingSalesman {
	vector<int> eg[51];
	int m;
	int ok[51][1024];
	public:
	int maxProfit(vector <int> cityValues, vector <string> roads) {
		int y,x,loop,n;
		char str[100];
		m=roads.size();
		FOR(y,m) {
			eg[y].clear();
			strcpy(str,roads[y].c_str());
			FOR(x,m) {
				if(str[x]=='Y') eg[y].push_back(x);
			}
		}
		ZERO(ok);
		int up=1;
		ok[0][cityValues[0]]=1;
		while(up) {
			up=0;
			FOR(x,m) {
				int id;
				FOR(n,1024) {
					if(ok[x][n]!=1) continue;
					FOR(id,eg[x].size()) {
						y = eg[x][id];
						int nv = n ^ cityValues[y];
						if(ok[y][nv]==0) up=ok[y][nv]=1;
					}
				}
			}
		}
		int mx=0;
		FOR(x,m) {
			FOR(n,1024) {
				if(ok[x][n]>0 && n>mx) mx=n;
			}
		}
		return mx;
		
	}
};

まとめ

最初、スタート地点を任意の点で良いと勘違いしていた。
それでもテストコードが通ってしまったのが難点。本番だったら爆死してたな…。