結果

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

ソースコード

diff # 

import sys
from itertools import permutations

def generate_group_sizes(m, num_groups):
    group_sizes_list = []
    def dfs(current, remaining, path):
        if len(path) == num_groups - 1:
            path = path + [remaining]
            group_sizes_list.append(path)
            return
        for i in range(1, remaining - (num_groups - len(path) - 1) + 1):
            dfs(current + i, remaining - i, path + [i])
    dfs(0, m, [])
    return group_sizes_list

def main():
    input = sys.stdin.read().split()
    n = int(input[0])
    cards = input[1:n+1]
    digits = [c for c in cards if c.isdigit()]
    ops = [c for c in cards if c in '+-']
    m = len(digits)
    k = len(ops)
    
    group_sizes_list = generate_group_sizes(m, k+1)
    
    max_val = -float('inf')
    min_val = float('inf')
    
    for group_sizes in group_sizes_list:
        if sum(group_sizes) != m or len(group_sizes) != k+1:
            continue
        seen_ops = set()
        for op_perm in permutations(ops):
            if op_perm in seen_ops:
                continue
            seen_ops.add(op_perm)
            
            # Compute max value
            sorted_desc = sorted(digits, key=lambda x: -int(x))
            remaining_desc = sorted_desc.copy()
            numbers_max = []
            valid = True
            for i in range(k+1):
                size = group_sizes[i]
                if len(remaining_desc) < size:
                    valid = False
                    break
                if i == 0:
                    group = remaining_desc[:size]
                    numbers_max.append(int(''.join(group)))
                    remaining_desc = remaining_desc[size:]
                else:
                    op = op_perm[i-1]
                    if op == '+':
                        group = remaining_desc[:size]
                        numbers_max.append(int(''.join(group)))
                        remaining_desc = remaining_desc[size:]
                    else:
                        if len(remaining_desc) < size:
                            valid = False
                            break
                        group = remaining_desc[-size:]
                        group = group[::-1]
                        numbers_max.append(int(''.join(group)))
                        remaining_desc = remaining_desc[:-size]
            if not valid:
                continue
            current_val = numbers_max[0]
            for i in range(k):
                if op_perm[i] == '+':
                    current_val += numbers_max[i+1]
                else:
                    current_val -= numbers_max[i+1]
            if current_val > max_val:
                max_val = current_val
            
            # Compute min value
            sorted_asc = sorted(digits, key=lambda x: int(x))
            remaining_asc = sorted_asc.copy()
            numbers_min = []
            valid = True
            for i in range(k+1):
                size = group_sizes[i]
                if len(remaining_asc) < size:
                    valid = False
                    break
                if i == 0:
                    group = remaining_asc[:size]
                    numbers_min.append(int(''.join(group)))
                    remaining_asc = remaining_asc[size:]
                else:
                    op = op_perm[i-1]
                    if op == '+':
                        group = remaining_asc[:size]
                        numbers_min.append(int(''.join(group)))
                        remaining_asc = remaining_asc[size:]
                    else:
                        if len(remaining_asc) < size:
                            valid = False
                            break
                        group = remaining_asc[-size:]
                        group = group[::-1]
                        numbers_min.append(int(''.join(group)))
                        remaining_asc = remaining_asc[:-size]
            if not valid:
                continue
            current_val_min = numbers_min[0]
            for i in range(k):
                if op_perm[i] == '+':
                    current_val_min += numbers_min[i+1]
                else:
                    current_val_min -= numbers_min[i+1]
            if current_val_min < min_val:
                min_val = current_val_min
    
    print(max_val, min_val)

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