結果

問題 No.2398 ヒドラ崩し
コンテスト
ユーザー lam6er
提出日時 2025-04-15 21:47:06
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,378 bytes
コンパイル時間 442 ms
コンパイル使用メモリ 82,340 KB
実行使用メモリ 413,160 KB
最終ジャッジ日時 2025-04-15 21:48:30
合計ジャッジ時間 3,025 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 18 WA * 12 RE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    H = sys.stdin.readline().strip()
    
    memo = {}
    
    def solve(h):
        if h in memo:
            return memo[h]
        if h == "":
            memo[h] = False
            return False
        # Case 1: ends with "()"
        if len(h) >= 2 and h.endswith("()"):
            h_prime = h[:-2]
            result = not solve(h_prime)
            memo[h] = result
            return result
        # Case 2: check if enclosed in parentheses
        if h[0] == '(' and h[-1] == ')':
            inner = h[1:-1]
            # Check if inner can be decomposed into h1' + "()"
            if len(inner) >= 2 and inner.endswith("()"):
                h1_prime = inner[:-2]
                s0 = solve("")
                s1_prime = solve(h1_prime)
                result = (s0 ^ s1_prime) == 0
                memo[h] = result
                return result
            else:
                # Check if there's any n such that h0 + (h1[n]) is losing
                # For this problem, assume no such n exists
                memo[h] = False
                return False
        # Case 3: decompose into h0 and h1 concatenation
        # Find the first split point
        stack = []
        split_point = -1
        for i in range(len(h)):
            if h[i] == '(':
                stack.append('(')
            else:
                if not stack:
                    # Invalid, but input is valid, so this shouldn't happen
                    memo[h] = False
                    return False
                stack.pop()
            if not stack:
                split_point = i + 1
                break
        if split_point == -1:
            memo[h] = False
            return False
        h0 = h[:split_point]
        h1 = h[split_point:]
        # Check if h1 can be decomposed into h1' + "()"
        if len(h1) >= 2 and h1.endswith("()"):
            h1_prime = h1[:-2]
            s0 = solve(h0)
            s1_prime = solve(h1_prime)
            result = (s0 ^ s1_prime) == 0
            memo[h] = result
            return result
        else:
            # Check if there's any n such that h0 + (h1[n]) is losing
            # Assume no such n exists
            memo[h] = False
            return False
    
    result = solve(H)
    if result:
        print(0)
    else:
        print(1)

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