結構難しかったようで…。
https://atcoder.jp/contests/dwacon5th-final-open/tasks/dwacon5th_final_a
問題
頂点が青・赤で塗られた木を成す無向グラフが与えられる。
ここで2人で交互にターンを迎えるゲームを行う。
今駒がある頂点にあるとき、自身のターンでは任意の隣接頂点に駒を動かす。
最終的に青頂点に駒が止まれば先手、赤頂点に止まれば後手の勝ちである。
2人の合計移動回数Kが与えられたとき、駒の初期位置全通りに対し、両者最適手を打った時の勝者を求めよ。
解法
残り手数が偶数で自分が勝者となる頂点におり、次に相手の手番となるケースでは、相手がどう動かそうと自分がそれを戻せば勝ち確定となる。
- Kが奇数の場合
- 初期状態で隣接頂点に青頂点があるとき、先手がそこに駒を移動させると上記勝ち確状態になる。
- そうでない場合、どこに動かしても後手が駒を初期位置に戻すので先手必敗である。
- Kが偶数の場合
- 初期位置が赤い場合、どこに動かしても後手が駒を初期位置に戻すので先手必敗である。
- そうでない場合、隣接頂点の中に「さらにその隣接頂点に赤頂点が1つもない」ようなものがあれば、そこに移動させれば後手に対し上記「Kが奇数の場合の必敗状態」に持ち込めるので先手が勝てる。
int N,M; ll K; string S; vector<int> E[101010]; int R[101010],B[101010]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M>>K>>S; FOR(i,M) { cin>>x>>y; x--,y--; E[x].push_back(y); E[y].push_back(x); ((S[x]=='B')?B[y]:R[y])=1; ((S[y]=='B')?B[x]:R[x])=1; } if(K%2==0) { FOR(i,N) { if(S[i]=='R') { cout<<"Second"<<endl; } else { x=0; FORR(e,E[i]) if(R[e]==0) x++; if(x) cout<<"First"<<endl; else cout<<"Second"<<endl; } } } else { FOR(i,N) { if(B[i]) { cout<<"First"<<endl; } else { cout<<"Second"<<endl; } } } }
まとめ
まぁこれは解けるかな…。