辺と点で操作を分ける対戦ゲーは珍しい?
https://yukicoder.me/problems/no/1582
問題
木を成す無向グラフが与えられる。
各頂点は初期状態で白く塗られている。
ここで2人交互に操作を行う対戦ゲームを行う。
先手は、両端が白頂点の辺を選び、両端の頂点を黒く塗る。
後手は、黒頂点を1つ選び、白く塗る。
先手が操作できなくなったら終了である。
先手は黒頂点、後手は白頂点を増やそうとするとき、最終的に黒頂点は何通りか。
解法
最終的に、白頂点が隣接しない塗り方のうち白頂点が最多のものとなる。
もし後手が希望しない塗り方があれば、その両端をいったん白くリセットし、先手に黒く塗らせたのち塗り替えればよいためである。
あとは、典型。
SubTree毎に根が白・黒頂点であるとき、SubTree内の白頂点の最大数を数えていこう。
int N; vector<int> E[202020]; int W[202020],B[202020]; void dfs(int cur,int pre) { W[cur]=1; FORR(e,E[cur]) if(e!=pre) { dfs(e,cur); W[cur]+=B[e]; B[cur]+=max(B[e],W[e]); } } void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N-1) { cin>>x>>y; E[x-1].push_back(y-1); E[y-1].push_back(x-1); } dfs(0,0); cout<<N-max(W[0],B[0])<<endl; }
まとめ
考察は手間だけど、実装は軽め。