ARC 064 D - An Ordinary Game

• 問題

問題概要

英小文字から成る文字列sが与えられる.
両端以外から,その両隣が同じ文字でないならば文字を1つ取り除け,文字が取り除けなくなったら負けというゲームをする.
先手と後手どちらが勝つか.

解法

ゲーム終了時の文字列は"abab..ab" または "abab..aba"となる.
両端の文字は変わらないから,s[0]==s[N-1]なら前者,そうでないなら後者になる.
上の終了時の文字列以外では必ず手があることに注意すると,
(ゲームの手数) = N-(最終文字列)の偶奇がわかる.
ゲームの手数の偶奇によって勝敗が決まるから, if (先頭==終端) xor (Nが偶数) -> 後手勝ち
else -> 先手勝ち となる.

メモ

最終的な文字列->考察できた
手数の偶奇に注目する->できなかった
最終的な文字列を具体的に求めようとしていたのが敗因っぽい.
こういうタイプの問題よく出る気がするので,手数の偶奇に注目するの覚えておこう.

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back
#define DEBUG false

using namespace std;

using ll = long long;
using P = pair<int,int>;
using Pl = pair<int,ll>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60;
const int MAX_N = 2003;
const ll lmod = 1e9+7;

int main(){
  string s; cin >> s; int N = s.size();
  cout << ((N%2==0 ^ s[0]==s[N-1]) ? "Second" : "First") << endl;
  return 0;
}