結果

問題 No.297 カードの数式
ユーザー gew1fw
提出日時 2025-06-12 19:51:31
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,886 bytes
コンパイル時間 179 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 65,168 KB
最終ジャッジ日時 2025-06-12 19:51:52
合計ジャッジ時間 2,182 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from itertools import combinations, permutations

def main():
    N = int(sys.stdin.readline())
    cards = sys.stdin.readline().split()
    digits = [c for c in cards if c.isdigit()]
    ops = [c for c in cards if c in '+-']
    O_list = []
    for O in range(1, (N-1)//2 +1):
        if 2*O +1 != N:
            continue
        O_list.append(O)
    max_val = -float('inf')
    min_val = float('inf')
    
    for O in O_list:
        available_positions = list(range(1, N-1))  # 0-based, positions 1 to N-2
        if O == 0:
            continue
        for op_positions in combinations(available_positions, O):
            valid = True
            for i in range(1, len(op_positions)):
                if op_positions[i] - op_positions[i-1] < 2:
                    valid = False
                    break
            if not valid:
                continue
            
            if len(ops) < O:
                continue
            unique_ops = list(permutations(ops, O))
            seen = set()
            for op_perm in unique_ops:
                if op_perm in seen:
                    continue
                seen.add(op_perm)
                
                expr = ['-'] * N
                for i, pos in enumerate(op_positions):
                    expr[pos] = op_perm[i]
                
                digit_indices = [i for i in range(N) if expr[i] == '-']
                digit_groups = []
                prev = 0
                for pos in op_positions:
                    if prev < pos:
                        group = []
                        for i in range(prev, pos):
                            if expr[i] == '-':
                                break
                            group.append(i)
                        digit_groups.append(group)
                        prev = pos + 1
                group = []
                for i in range(prev, N):
                    if expr[i] != '-':
                        group.append(i)
                if group:
                    digit_groups.append(group)
                
                if len(digit_groups) != O + 1:
                    continue
                
                groups = []
                for dg in digit_groups:
                    group_digits = []
                    for idx in dg:
                        if expr[idx] == '-':
                            break
                        group_digits.append(cards[idx])
                    groups.append(group_digits)
                
                max_nums = []
                min_nums = []
                for g in groups:
                    if not g:
                        continue
                    sorted_desc = sorted(g, reverse=True)
                    max_num = int(''.join(sorted_desc))
                    max_nums.append(max_num)
                    sorted_asc = sorted(g)
                    min_num = int(''.join(sorted_asc))
                    min_nums.append(min_num)
                
                for choice in product([0, 1], repeat=len(groups)):
                    current = 0
                    valid_expr = True
                    for i in range(len(groups)):
                        if choice[i] == 0:
                            num = max_nums[i]
                        else:
                            num = min_nums[i]
                        if i == 0:
                            current = num
                        else:
                            op = op_perm[i-1]
                            if op == '+':
                                current += num
                            else:
                                current -= num
                    if current > max_val:
                        max_val = current
                    if current < min_val:
                        min_val = current
    print(max_val, min_val)

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