気づき系。。。
こういうのを一瞬で思いつける人になりたい。

問題概要

長さ $N$ の文字列 $S$ が与えられる。先手と後手とで交互に

文字列中の文字を一文字選んで消していく、ただし
- 両端は消せない
- その文字を消すことで「同じ文字が隣り合っている箇所」が発生するなら消せない

先に操作を行えなくなった方が負け。双方最善を尽くしたときに先手と後手のどちらが勝つか？

制約

$3 \le N \le 10^{5}$

考えたこと

ゲームというと

アドホック
一気に盤面を進められる構造があって、実質に選べる選択肢が少ない
Nim とか Grundy とか
DP

なイメージがあって、あんまり多くの方針をとれない感がある。今回は状態量があまりにも多すぎて思考停止で DP とかはできそうもないし、1 文字ずつ減っていくし...

こうなると AtCoder だと、こういうときパリティに注目することが多い気がする。なにかしら毎ターン不変、もしくは入れ替わるような量が見つけられる気がする。

そして今回は、とりわけ 1 文字ずつ減っていくなら、最終局面の文字数だけで勝敗が決まってしまうことがわかる。

そして今回の終局場面を考えると

xyxyxyx
xyxyxy

みたいに、必ず 2 文字が交互になってる形で終わることがわかる。最初はどの 2 文字を最後に残すのかを戦略的に決めていくゲームだとばかり思った。。。

けど、よく考えたら両端消せないのだから、両端だけで最終局面の文字列の形が決まってしまうことがわかる。xy が何個繰り返すかまでは自由度があれど、偶奇は最初から決まってることがわかる。

以上から「消せる文字の個数の偶奇」が最初からわかっているので、それが偶数なら後手勝ち、奇数なら先手勝ち。

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s; cin >> s;
    if (s[0] == s.back()) {
        if (s.size() & 1) puts("Second");
        else puts("First");
    }
    else {
        if (s.size() & 1) puts("First");
        else puts("Second");
    }
}