結果

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

ソースコード

diff # 

import itertools
from collections import defaultdict

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    cards = data[1:N+1]
    
    digits = []
    operators = []
    for c in cards:
        if c in '+-':
            operators.append(c)
        else:
            digits.append(c)
    
    D = len(digits)
    O = len(operators)
    k = O + 1
    
    max_val = -float('inf')
    min_val = float('inf')
    
    # Generate all possible splits into k groups
    split_positions = list(range(1, D))
    for splits in itertools.combinations(split_positions, O):
        splits = sorted(splits)
        groups = []
        prev = 0
        for s in splits:
            groups.append(digits[prev:s])
            prev = s
        groups.append(digits[prev:])
        
        # Form numbers from groups
        numbers = []
        for group in groups:
            num_str = ''.join(group)
            num = int(num_str)
            numbers.append(num)
        
        plus = operators.count('+')
        minus = O - plus
        
        # Initialize DP
        dp = defaultdict(lambda: (-float('inf'), float('inf')))
        initial_state = (0, plus, minus)
        dp[initial_state] = (numbers[0], numbers[0])
        
        for step in range(k-1):
            current_number = numbers[step + 1]
            current_states = [key for key in dp if key[0] == step]
            for state in current_states:
                current_step, p, m = state
                current_max, current_min = dp[state]
                
                # Apply '+'
                if p > 0:
                    new_p = p - 1
                    new_m = m
                    new_value_max = current_max + current_number
                    new_value_min = current_min + current_number
                    new_state = (step + 1, new_p, new_m)
                    existing_max, existing_min = dp.get(new_state, (-float('inf'), float('inf')))
                    new_max = max(existing_max, new_value_max)
                    new_min = min(existing_min, new_value_min)
                    dp[new_state] = (new_max, new_min)
                
                # Apply '-'
                if m > 0:
                    new_p = p
                    new_m = m - 1
                    new_value_max = current_max - current_number
                    new_value_min = current_min - current_number
                    new_state = (step + 1, new_p, new_m)
                    existing_max, existing_min = dp.get(new_state, (-float('inf'), float('inf')))
                    new_max = max(existing_max, new_value_max)
                    new_min = min(existing_min, new_value_min)
                    dp[new_state] = (new_max, new_min)
        
        # Collect results from final states
        final_step = k - 2
        for state in dp:
            s, p, m = state
            if s == final_step and p == 0 and m == 0:
                current_max, current_min = dp[state]
                if current_max > max_val:
                    max_val = current_max
                if current_min < min_val:
                    min_val = current_min
    
    print(max_val, min_val)

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