結果

問題 No.297 カードの数式
ユーザー lam6er
提出日時 2025-03-26 15:53:30
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,575 bytes
コンパイル時間 246 ms
コンパイル使用メモリ 81,972 KB
実行使用メモリ 77,268 KB
最終ジャッジ日時 2025-03-26 15:54:15
合計ジャッジ時間 2,332 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from itertools import permutations, combinations

def main():
    input = sys.stdin.read().split()
    N = int(input[0])
    cards = input[1:N+1]
    
    digits = []
    ops = []
    for c in cards:
        if c in '+-':
            ops.append(c)
        else:
            digits.append(c)
    op_count = len(ops)
    k = op_count + 1
    num_digits = len(digits)
    
    if op_count == 0:
        print(''.join(digits))
        return
    
    from itertools import chain, combinations
    def generate_splits(n, k):
        if k == 1:
            return [[n]]
        splits = []
        for c in combinations(range(1, n), k-1):
            prev = 0
            parts = []
            for pos in c:
                parts.append(pos - prev)
                prev = pos
            parts.append(n - prev)
            splits.append(parts)
        return splits
    
    splits = generate_splits(num_digits, k)
    
    unique_ops = {}
    for p in set(permutations(ops)):
        unique_ops[p] = True
    op_perms = list(unique_ops.keys())
    
    max_val = -float('inf')
    min_val = float('inf')
    
    for split in splits:
        for op_perm in op_perms:
            sorted_desc = sorted(digits, key=lambda x: -int(x))
            groups_max = []
            remaining = sorted_desc.copy()
            current_val = 0
            for i in range(k):
                s = split[i]
                if i == 0:
                    group = remaining[:s]
                    remaining = remaining[s:]
                    groups_max.append(int(''.join(group)))
                else:
                    op = op_perm[i-1]
                    if op == '+':
                        group = remaining[:s]
                        remaining = remaining[s:]
                        groups_max.append(int(''.join(group)))
                    else:
                        group = remaining[-s:]
                        remaining = remaining[:-s]
                        groups_max.append(int(''.join(sorted(group))))
            expr_val = groups_max[0]
            for i in range(len(op_perm)):
                if op_perm[i] == '+':
                    expr_val += groups_max[i+1]
                else:
                    expr_val -= groups_max[i+1]
            if expr_val > max_val:
                max_val = expr_val
            
            sorted_asc = sorted(digits, key=lambda x: int(x))
            groups_min = []
            remaining = sorted_asc.copy()
            for i in range(k):
                s = split[i]
                if i == 0:
                    group = remaining[:s]
                    remaining = remaining[s:]
                    groups_min.append(int(''.join(group)))
                else:
                    op = op_perm[i-1]
                    if op == '+':
                        group = remaining[:s]
                        remaining = remaining[s:]
                        groups_min.append(int(''.join(sorted(group))))
                    else:
                        group = remaining[-s:]
                        remaining = remaining[:-s]
                        groups_min.append(int(''.join(sorted(group, reverse=True))))
            expr_val_min = groups_min[0]
            for i in range(len(op_perm)):
                if op_perm[i] == '+':
                    expr_val_min += groups_min[i+1]
                else:
                    expr_val_min -= groups_min[i+1]
            if expr_val_min < min_val:
                min_val = expr_val_min
    
    print(f"{max_val} {min_val}")

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