Official

R - Bracket Game Editorial by toam


? の個数を \(c\) とします.

[1] \(c=0\) のとき

勝敗はすでに決まっています.

[2] \(c\) が偶数のとき

後手が最後の手番で \(S\) が括弧列にならないような文字に必ず置き換えることができるので,後手必勝です.

[3] \(c\) が奇数のとき

正しい括弧列であるための必要条件に,\(S\) に含まれている () の個数が等しいことがあります.

() の個数の差が \(3\) 個以上のとき,後手は直前の先手が置き換えた文字とは違う文字に置き換えることで,() の個数の差をつねに \(2\) 以上にすることができるため後手必勝です.

)( の個数の差が \(1\) 個のときを考えます.\(1\) 手目で ? から置き換える文字は () のうち少ないほうです.その後,先手は直前の後手が置き換えた文字とは違う文字に置き換えることで,先手の操作直後の )( の個数の差を \(0\) 個にすることができます.

ここで,以下が成り立ちます.

  • 先手が ( を置く場合,? のうち最も左の場所を置き換えるのが最適である.
  • 先手が ) を置く場合,? のうち最も右の場所を置き換えるのが最適である.
  • 後手が ( を置く場合,? のうち最も右の場所を置き換えるのが最適である.
  • 後手が ) を置く場合,? のうち最も左の場所を置き換えるのが最適である.

よって,? の場所を昇順に列挙した列を \((x_1,x_2,\ldots,x_m)\) とすると,ゲームが終了した後の \(S\) は以下のようになっています.

  • \(1\) 手目で先手が ( に置き換えるとき:\(S_{x_1}S_{x_2}S_{x_3}\ldots S_{x_m}=\texttt{()()(...()(}\)
  • \(1\) 手目で先手が ) に置き換えるとき:\(S_{x_1}S_{x_2}S_{x_3}\ldots S_{x_m}=\texttt{)()()...)()}\)

このように置き換えたときに \(S\) が正しい括弧列になるかどうかを判定すればよいです.

def is_valid(s):
    tmp = 0
    for i in s:
        if i == "(":
            tmp += 1
        else:
            tmp -= 1
        if tmp < 0:
            return False
    return tmp == 0


def solve():
    s = input()
    s1 = list(s)
    s2 = list(s)
    cnt = 0
    n = len(s)
    for i in range(n):
        if s[i] == "?":
            cnt += 1
            s1[i] = "()"[cnt & 1]
            s2[i] = ")("[cnt & 1]
    if cnt == 0:
        return is_valid(s)
    if cnt % 2 == 1:
        return is_valid(s1) or is_valid(s2)
    return False


for _ in range(int(input())):
    print("First" if solve() else "Second")

posted:
last update: