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; } };