第5回 ドワンゴからの挑戦状 本戦 : A - Taro vs. Jiro

結構難しかったようで…。
https://atcoder.jp/contests/dwacon5th-final-open/tasks/dwacon5th_final_a

問題

頂点が青・赤で塗られた木を成す無向グラフが与えられる。
ここで２人で交互にターンを迎えるゲームを行う。
今駒がある頂点にあるとき、自身のターンでは任意の隣接頂点に駒を動かす。
最終的に青頂点に駒が止まれば先手、赤頂点に止まれば後手の勝ちである。

２人の合計移動回数Kが与えられたとき、駒の初期位置全通りに対し、両者最適手を打った時の勝者を求めよ。

解法

残り手数が偶数で自分が勝者となる頂点におり、次に相手の手番となるケースでは、相手がどう動かそうと自分がそれを戻せば勝ち確定となる。

• Kが奇数の場合
  • 初期状態で隣接頂点に青頂点があるとき、先手がそこに駒を移動させると上記勝ち確状態になる。
  • そうでない場合、どこに動かしても後手が駒を初期位置に戻すので先手必敗である。
• Kが偶数の場合
  • 初期位置が赤い場合、どこに動かしても後手が駒を初期位置に戻すので先手必敗である。
  • そうでない場合、隣接頂点の中に「さらにその隣接頂点に赤頂点が１つもない」ようなものがあれば、そこに移動させれば後手に対し上記「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;
			}
		}
	}
}

まとめ

まぁこれは解けるかな…。