D - An Ordinary Game AtCoder Regular Contest 064

D - An Ordinary Game

問題概略

長さ3以上の文字列sが与えられる。二人でゲームを行う。

sから両端以外の文字を一つ取り除く。ただし、その結果同じ文字が隣り合ってはいけない。

先に操作を行えなくなったほうが負け。

制約

• $3\le |s|\le {10}^5$
• $s$ は英小文字のみからなる。
• $s$ の中に同一の文字が隣り合う箇所はない。

解法

ゲームなのでこういう盤面の時に勝つ。という表を作って埋めようとしたがうまく行かなかった。

今回はゲーム終了時の盤面について考える。

実が両端が違う文字の場合　と　同じ文字の場合で

ababab

abcba

のように偶数と奇数になる。

よってそのようにする。

問題の芯

ゲーム終了時から考えてみる。

 public static void main(String[] args)
    {
        char[] s = sc.next().toCharArray();
        N=s.length;
        if(s[0] == s[s.length-1]){
            if(N % 2 ==0){
                System.out.println("First");
            }else{
                System.out.println("Second");
            }
        }else{
            if(N % 2 ==1){
                System.out.println("First");
            }else{
                System.out.println("Second");
            }
        }
    }