TopCoderOpen 2013 Round2B Medium ScotlandYard

TCOで解けてなかった問題を復習。
http://community.topcoder.com/stat?c=problem_statement&pm=12519

問題

N個の都市があり、それぞれの都市の間に有向グラフ辺の形でバス・タクシー・地下鉄による移動の可否が与えられる。
このグラフを用いて、CielとJiroでゲームを行う。
Cielは任意の都市から開始し、バス・タクシー・地下鉄のいずれかを用いて隣接都市に移動していく。
移動できない場合、そのターンを完了できずゲーム終了。
移動する場合、CielはJiroに利用した乗り物を告げる。
その乗り物履歴を用いてJiroがCielの居場所を特定できた場合、そのターン後にゲーム終了となる。

Cielの移動可能なターン数を最大化せよ。

解法

最初思いついたのは、都市の冪集合の遷移を考えること。
すなわち、初期状態は「全都市に存在可能」から始まり、バス・タクシー・地下鉄を用いた時にそれぞれ存在可能な都市の集合が遷移するので、２都市以上に存在可能なターン数が何ターンか繰り返す。
ただこの処理は、都市の冪集合で2^Nの状態が存在するためN<=50では不可。

ここで、実は別に全都市の存在可否を覚える必要がないことがわかる。
どこか２都市以上に存在していればゲームは終了しない。
よって、2^Nすべての状態を持つのではなく、「ある２つの都市の両方に存在可能」かどうかの状態だけ考え、その状態を点として持つ有向グラフを考えればよい。
そしてその有向グラフの最長経路を答える。これなら状態はO(N^2)ですむ。

class ScotlandYard {
	int N;
	int M[3][51][51],dp[51][51];
	
	public:
	int dfs(int x,int y) {
		int z,ty,x2,y2;
		if(dp[x][y]==-1) {
			dp[x][y]=10000;
			int ma=0;
			
			FOR(ty,3) {
				ll mask=0;
				FOR(z,N) if(M[ty][x][z] || M[ty][y][z]) mask |= 1LL<<z;
				if(__builtin_popcountll(mask)==1) ma=max(ma,1);
				FOR(y2,N) FOR(x2,y2) {
					if((mask & (1LL<<x2))==0 || (mask & (1LL<<y2))==0) continue;
					ma=max(ma,1+dfs(x2,y2));
				}
			}
			dp[x][y]=ma;
		}
		return dp[x][y];
	}
	
	
	int maxMoves(vector <string> taxi, vector <string> bus, vector <string> metro) {
		int i,j,x,y,z,x2,y2;
		N=taxi.size();
		ZERO(M);
		FOR(x,N) FOR(y,N) {
			M[0][x][y] = (taxi[x][y]=='Y');
			M[1][x][y] = (bus[x][y]=='Y');
			M[2][x][y] = (metro[x][y]=='Y');
		}
		MINUS(dp);
		
		int ret=0;
		FOR(y,N) FOR(x,y) ret = max(ret,dfs(x,y));
		return (ret>=10000) ? -1 : ret;
	}
};

まとめ

２都市の状態だけ持てばよい、ってのが目からうろこだった。