結果
問題 |
No.2398 ヒドラ崩し
|
ユーザー |
![]() |
提出日時 | 2025-04-16 15:43:21 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,378 bytes |
コンパイル時間 | 626 ms |
コンパイル使用メモリ | 81,664 KB |
実行使用メモリ | 412,416 KB |
最終ジャッジ日時 | 2025-04-16 15:46:18 |
合計ジャッジ時間 | 2,738 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 18 WA * 12 RE * 1 |
ソースコード
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()