TopCoder SRM 670 Div1 Medium、Div2 Hard Treestrat

Warshall-Floyedの処理順間違えたけど通った。
http://community.topcoder.com/stat?c=problem_statement&pm=13990

問題

N頂点の木を成すグラフが与えられる。
初期状態で幾つかの頂点に赤いトークン、異なるいくつかの頂点に青いトークンが置かれている。

これを２人で以下のように交互に移動させる。
２人がそれぞれ操作を行うと１ターン終了である。

• 先手は、全赤トークンに対して同時に、その場に留めるか隣接点に移動させる。
• 後手は、全青トークンに対して同時に、その場に留めるか隣接点に移動させる。

途中、どこかの頂点で赤トークンと青トークンがともに存在する頂点があるとそこでゲーム終了である。
先手は終了ターン数を最大化、後手は最小化するようにトークンを動かした場合、何ターンで終了するか。

解法

このルールでは、先手は逃げ切ることはできない。
まずグラフは木なので、閉路を使って無限に逃げ切ることもできないし、赤と青は交互に移動するのですれ違うこともできない。

iターンで青トークンを配置可能な頂点を列挙したとき、各赤トークンがiターン以内に移動できるどの頂点も青トークンが配置可能であれば、そのターンで必ず終了する(よう後手が動くことができる)。

class Treestrat {
	public:
	int roundcnt(vector <int> tree, vector <int> A, vector <int> B) {
		int mat[61][61];
		ll mask[51][51]={};
		int N=tree.size()+1;
		
		int i,x,y,z;
		
		FOR(x,N) FOR(y,N) mat[x][y]=(x!=y)*1010;
		FOR(i,N-1) mat[i+1][tree[i]]=mat[tree[i]][i+1]=1;
		FOR(z,N) FOR(x,N) FOR(y,N) mat[x][y]=min(mat[x][y],mat[x][z]+mat[z][y]);
		
		FOR(x,N) FOR(i,51) FOR(y,N) if(mat[x][y]<=i) mask[x][i] |= 1LL<<y;
		
		for(i=0;i<=50;i++) {
			ll cm=0;
			FORR(b,B) cm |= mask[b][i];
			FORR(a,A) if((mask[a][i] & cm)==mask[a][i]) return i;
		}
	}
}

まとめ

300ptのDiv1 Easyが900pt のDiv2 Hardとなることはあるけど、450ptのDiv1 MediumはDiv2 Hardで1050pt扱いになるのか。