結果

問題 No.334 門松ゲーム
コンテスト
ユーザー koheijkt
提出日時 2025-12-30 15:01:30
言語 PyPy3
(8.0.0 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 1,103 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 96 ms
コンパイル使用メモリ 64,840 KB
実行使用メモリ 59,512 KB
最終ジャッジ日時 2026-10-15 04:05:06
合計ジャッジ時間 2,456 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge5_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from itertools import combinations
N = int(input())
K = list(map(int, input().split()))

DP = [-1]*(1<<N)
# DP[-1] が答え

def kadomatsu_check(a, b, c):
    return (b < a and b < c) or (b > a and b > c)

for i in range(1<<N):
    nums = []
    for j in range(N):
        if (i >> j) & 1 == 1:
            nums.append(j)
    if len(nums) < 3:
        continue
    for a, b, c in combinations(nums, 3):
        if kadomatsu_check(K[a], K[b], K[c]): # a, b, c を取り除いた集合に到達できる
            dst = i ^ (1<<a) ^ (1<<b) ^ (1<<c)
            #dst = i - (1<<a) - (1<<b) - (1<<c)
            if DP[dst] == -1:
                DP[i] = 1

if DP[-1] == -1:
    exit(print(-1))

# DP の復元
# DP[-1] から一手で進める正着を洗い出し、辞書順最小を見つける
ansl = []
# 1<<N から 3ビット減らす
for a, b, c in combinations([i for i in range(N)], 3):
    if kadomatsu_check(K[a], K[b], K[c]):
        if DP[((1<<N) - 1) ^ (1<<a) ^ (1<<b) ^ (1<<c)] == -1: #相手を-1に導けるのが第一打
            ansl.append((a, b, c))

ansl.sort()
print(*ansl[0])
0