Particle

競技プログラミングについての雑記

SRM 670 Div1 Medium Treestrat

まず、木なので高々 N ステップでゲームが終了する。
A のトークンは複数あるが、すべて独立に計算できるので、それぞれ別に計算する。
A のトークンが 1 つの場合は、BFS を行うことで、解が計算できる。

#define N 55
int d[N][N];
class Treestrat {
	public:
	int roundcnt(vector <int> t, vector <int> A, vector <int> B) {
		int n = t.size()+1;
		int m = n-1;
		int res = N;
		for(auto x: A){
			mset(d, 0);
			for(auto y: B) d[0][y] |= 1;
			d[0][x] |= 2;
			int cnt = 0;
			while(true){
				memcpy(d[cnt+1], d[cnt], sizeof(d[0]));
				rep(i, m){
					int u = i+1, v = t[i];
					d[cnt+1][u] |= d[cnt][v];
					d[cnt+1][v] |= d[cnt][u];
				}
				bool ok = false;
				++cnt;
				rep(i, n) if(d[cnt][i]==2) ok = true;
				if(!ok) break;
			}
			chmin(res, cnt);
		}
		return res;
	}
};