結果

問題 No.334 門松ゲーム
ユーザー lam6er
提出日時 2025-03-20 20:18:43
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 54 ms / 2,000 ms
コード長 1,324 bytes
コンパイル時間 169 ms
コンパイル使用メモリ 82,188 KB
実行使用メモリ 63,776 KB
最終ジャッジ日時 2025-03-20 20:19:35
合計ジャッジ時間 1,658 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

import itertools

def main():
    n = int(input())
    K = list(map(int, input().split()))
    
    valid_moves = []
    # Precompute all valid Kadomatsu triples (a, b, c)
    for a, b, c in itertools.combinations(range(n), 3):
        x, y, z = K[a], K[b], K[c]
        if x == y or y == z or x == z:
            continue
        sorted_xyz = sorted([x, y, z])
        mid_val = sorted_xyz[1]
        if mid_val == x or mid_val == z:
            valid_moves.append((a, b, c))
    
    if not valid_moves:
        print(-1)
        return
    
    max_mask = 1 << n
    dp = [False] * max_mask
    
    # Process masks in reverse order to fill DP table correctly
    for mask in reversed(range(max_mask)):
        for a, b, c in valid_moves:
            abc_mask = (1 << a) | (1 << b) | (1 << c)
            if (mask & abc_mask) == 0:
                new_mask = mask | abc_mask
                if not dp[new_mask]:
                    dp[mask] = True
                    break  # Only one winning move needed
    
    # Check if D can win by selecting any initial valid move
    for a, b, c in valid_moves:
        abc_mask = (1 << a) | (1 << b) | (1 << c)
        new_mask = abc_mask
        if not dp[new_mask]:
            print(f"{a} {b} {c}")
            return
    
    print(-1)

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