結果

問題 No.2398 ヒドラ崩し
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 19:43:05
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,722 bytes
コンパイル時間 431 ms
コンパイル使用メモリ 82,020 KB
実行使用メモリ 292,352 KB
最終ジャッジ日時 2025-06-12 19:43:11
合計ジャッジ時間 5,472 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20 WA * 6 TLE * 1 -- * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    sys.setrecursionlimit(1 << 25)
    h = sys.stdin.readline().strip()

    memo = {}
    def grundy(s):
        if s in memo:
            return memo[s]
        if not s:
            return 0
        # Try to split as s' + "()" first
        # Find the last occurrence of "()" as possible
        stack = []
        last_pos = -1
        for i, c in enumerate(s):
            if c == '(':
                stack.append(i)
            else:
                if stack:
                    start = stack.pop()
                    if i == start + 1:
                        last_pos = start
        if last_pos != -1:
            s_prime = s[:last_pos]
            g = grundy(s_prime)
            memo[s] = g + 1
            return g + 1
        # Otherwise, split as s0 + "(s1)"
        # Find the first possible split
        stack = []
        for i, c in enumerate(s):
            if c == '(':
                stack.append(i)
            else:
                if stack:
                    start = stack.pop()
                    if start == 0:
                        s0 = s[:start]
                        s1 = s[start+1:i]
                        g0 = grundy(s0)
                        g1 = grundy(s1)
                        mex = 0
                        seen = set()
                        seen.add(g0 ^ (g1 + 1))
                        while mex in seen:
                            mex += 1
                        memo[s] = mex
                        return mex
        # If neither can be split, it's dead
        memo[s] = 0
        return 0

    g = grundy(h)
    if g == 0:
        print(1)
    else:
        print(0 if g % 2 == 1 else 1)

if __name__ == "__main__":
    main()
0