結果

問題 No.946 箱箱箱
ユーザー lam6er
提出日時 2025-03-20 21:09:32
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 186 ms / 2,000 ms
コード長 613 bytes
コンパイル時間 218 ms
コンパイル使用メモリ 82,376 KB
実行使用メモリ 77,556 KB
最終ジャッジ日時 2025-03-20 21:10:23
合計ジャッジ時間 9,787 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 51
権限があれば一括ダウンロードができます

ソースコード

diff # 

n = int(input())
A = [int(input()) for _ in range(n)]

# Compute prefix xor sums (1-based)
xor_sum = [0] * (n + 1)
for i in range(1, n+1):
    xor_sum[i] = xor_sum[i-1] ^ A[i-1]

# Initialize DP array
G = [0] * (n + 2)  # G[1..n+1]

for i in range(n, 0, -1):
    s = set()
    max_k = n - i + 1
    for k in range(1, max_k + 1):
        j = i + k - 1
        y = xor_sum[j] ^ xor_sum[i-1]
        next_i = i + k
        g_next = G[next_i]
        val = y ^ g_next
        s.add(val)
    mex = 0
    while mex in s:
        mex += 1
    G[i] = mex

if G[1] != 0:
    print("Takahashi")
else:
    print("Takanashi")
0