結果

問題 No.334 門松ゲーム
コンテスト
ユーザー 学ぶマン
提出日時 2025-12-30 15:01:30
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 105 ms / 2,000 ms
コード長 1,103 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 292 ms
コンパイル使用メモリ 82,352 KB
実行使用メモリ 76,884 KB
最終ジャッジ日時 2025-12-30 15:01:33
合計ジャッジ時間 2,362 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

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