第5回 ドワンゴからの挑戦状 本選（オープンコンテスト）

A問題 Taro vs. Jiro (500)

A - Taro vs. Jiro

概要

赤と青に塗り分けられた無向単純連結グラフがある。
このグラフ上の一つの頂点にコマを置き、先手・後手で交互に動かすゲームを考える。
合わせて回動かし最終的に青の頂点にコマがあれば先手の勝ち、赤の頂点にコマがあれば後手の勝ちとする。
各頂点について、その頂点にコマがある状態からゲームを開始した場合の勝者を答えよ。

方針

場合分け。
(1)赤頂点、偶数回なら後手の勝ち

• どのように先手が動かしても、後手で元の赤頂点に戻れる。

(2)奇数回なら、先手が青頂点に動かせれば先手の勝ち。そうでないなら後手の勝ち。

• 先手が青に動かすことで、その後後手がどのように動かしても、先手で元の青頂点に戻れる。

(3)それ以外なら、「全ての1手先について、2手先に赤が存在する」なら後手の勝ち。そうでないなら先手の勝ち。
また、毎回探索するとTLEするようなので、各頂点について「1手先に青があるか」「1手先に赤があるか」「全ての1手先について2手先に赤があるか」を前もって計算する。

解答

Submission #3859803 - 第5回 ドワンゴからの挑戦状 本選（オープンコンテスト）

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
const int max_n = 100007;
vector<int> edge[max_n];
int n, m;
ll k;
string s;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	cin >> n >> m >> k;
	cin >> s;
	rep(i, m){
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		edge[a].push_back(b);
		edge[b].push_back(a);
	}
 
	// 1手先に青が存在するか
	bool n1b[n];
	rep(i, n){
		n1b[i] = false;
		for(int x : edge[i]){
			if(s[x] == 'B'){
				n1b[i] = true;
				break;
			}
		}
	}
 
	// 1手先に赤が存在するか
	bool n1r[n];
	rep(i, n){
		n1r[i] = false;
		for(int x : edge[i]){
			if(s[x] == 'R'){
				n1r[i] = true;
				break;
			}
		}
	}
 
	// 全ての1手先について2手先に赤が存在するか
	bool n2r[n];
	rep(i, n){
		n2r[i] = true;
		for(int x : edge[i]){
			if(!n1r[x]) {
				n2r[i] = false;
				break;
			}
		}
	}
 
	rep(i, n){
		if(s[i] == 'R' && k % 2 == 0){
			// 後手の勝ち
			// 先手がどこに行っても元の頂点に戻ればよい
			cout << "Second" << endl;
		}else if(k % 2 == 1){
			// 1手先に青があれば先手の勝ち
			// 先手で青に行ければ、あとは後手がどこに行っても元の頂点に戻ればよい
			cout << (n1b[i] ? "First" : "Second") << endl;
		}else{
			// s[i] == 'B' && k % 2 == 0
			// 任意の1手先について2手先に赤が存在したら後手の勝ち
			cout << (n2r[i] ? "Second" : "First") << endl;
		}
	}
}