結果

問題 No.2398 ヒドラ崩し
ユーザー lam6er
提出日時 2025-04-15 21:47:09
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,669 bytes
コンパイル時間 642 ms
コンパイル使用メモリ 81,948 KB
実行使用メモリ 225,784 KB
最終ジャッジ日時 2025-04-15 21:48:38
合計ジャッジ時間 7,206 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19 WA * 7 RE * 1 TLE * 1 -- * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    s = sys.stdin.readline().strip()
    
    def is_case1(s):
        return s.endswith("()")
    
    def parse_case2(s):
        if not s:
            return None, None
        if s[-1] != ')':
            return None, None
        stack = []
        start = -1
        for i in range(len(s)):
            if s[i] == '(':
                stack.append(i)
            elif s[i] == ')':
                if stack:
                    start = stack.pop()
                    if not stack and i == len(s) - 1:
                        h0 = s[:start]
                        h1 = s[start+1:i]
                        if is_case1(h1):
                            h1_prime = h1[:-2]
                            return h0, h1_prime
        return None, None
    
    def parse_case3(s):
        if not s:
            return None, None
        if s[-1] != ')':
            return None, None
        stack = []
        start = -1
        for i in range(len(s)):
            if s[i] == '(':
                stack.append(i)
            elif s[i] == ')':
                if stack:
                    start = stack.pop()
                    if not stack and i == len(s) - 1:
                        h0 = s[:start]
                        h1 = s[start+1:i]
                        return h0, h1
        return None, None
    
    memo = {}
    
    def solve(s):
        if s in memo:
            return memo[s]
        if not s:
            memo[s] = 1
            return 1
        if is_case1(s):
            h_prime = s[:-2]
            res = 1 - solve(h_prime)
            memo[s] = res
            return res
        else:
            h0, h1_prime = parse_case2(s)
            if h0 is not None:
                a = solve(h0)
                b = solve(h1_prime)
                if a == 1 or b == 1:
                    memo[s] = 0
                    return 0
                else:
                    memo[s] = 1
                    return 1
            else:
                h0, h1 = parse_case3(s)
                if h0 is not None:
                    a = solve(h0)
                    def can_win(h1_part):
                        if not h1_part:
                            return False
                        if is_case1(h1_part):
                            h1_prime_part = h1_part[:-2]
                            return (1 - solve(h1_prime_part)) == (1 - a)
                        else:
                            h0_part, h1p_part = parse_case2(h1_part)
                            if h0_part is not None:
                                a_part = solve(h0_part)
                                b_part = solve(h1p_part)
                                if a_part == 1 or b_part == 1:
                                    return 0 == (1 - a)
                                else:
                                    return 1 == (1 - a)
                            else:
                                h0_part3, h1_part3 = parse_case3(h1_part)
                                if h0_part3 is not None:
                                    a_part3 = solve(h0_part3)
                                    return can_win(h1_part3)
                                else:
                                    return False
                    exists = can_win(h1)
                    if exists:
                        memo[s] = 0
                        return 0
                    else:
                        memo[s] = 1
                        return 1
                else:
                    memo[s] = 1
                    return 1
    
    result = solve(s)
    print(result if result in (0, 1) else -1)

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