結果

問題 No.2145 Segment +-
ユーザー lam6er
提出日時 2025-04-09 20:58:13
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 4,303 bytes
コンパイル時間 503 ms
コンパイル使用メモリ 82,600 KB
実行使用メモリ 79,208 KB
最終ジャッジ日時 2025-04-09 21:00:37
合計ジャッジ時間 3,266 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 11 RE * 13
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import defaultdict

def main():
    sys.setrecursionlimit(1 << 25)
    N = int(sys.stdin.readline())
    S = sys.stdin.readline().strip()

    # DP state: key is (current_sum, min_sum_end), value is (current_boost, flip_count)
    dp = defaultdict(lambda: defaultdict(lambda: float('inf')))
    # Initial state before any elements are processed
    dp[0][0] = (0, 0)  # (min_sum_end) : (current_boost, flip_count)

    for i in range(N):
        new_dp = defaultdict(lambda: defaultdict(lambda: float('inf')))
        c = S[i]
        possibilities = []
        if c == '+':
            possibilities.append(1)
        elif c == '-':
            possibilities.append(-1)
        else:
            possibilities.extend([1, -1])

        for prev_prefix_sum in list(dp.keys()):
            for prev_min_sum_end in dp[prev_prefix_sum]:
                current_boost, flip_count = dp[prev_prefix_sum][prev_min_sum_end]

                current_sum_before = prev_prefix_sum + current_boost

                for val in possibilities:
                    new_prefix_sum = prev_prefix_sum + val
                    new_min_sum_end = min(val, prev_min_sum_end + val)
                    new_current_sum_before_flip = current_sum_before + val

                    if new_current_sum_before_flip >= 0:
                        new_current_boost = current_boost
                        new_flip_count = flip_count
                        key_new_prefix = new_prefix_sum
                        if new_flip_count < new_dp[key_new_prefix].get(new_min_sum_end, float('inf')):
                            new_dp[key_new_prefix][new_min_sum_end] = (new_current_boost, new_flip_count)
                    else:
                        delta = -2 * new_min_sum_end
                        new_flip_count = flip_count + 1
                        new_current_boost = current_boost + delta
                        key_new_prefix = new_prefix_sum
                        # Compute new current_sum_after_flip
                        # new_prefix_sum + new_current_boost = (prev_prefix_sum + val) + (current_boost + delta)
                        # = prev_prefix_sum + val + current_boost + delta
                        # but delta = -2 * new_min_sum_end
                        # and new_current_boost = current_boost + delta
                        # So the new_current_sum_after_flip is new_prefix_sum + new_current_boost = new_prefix_sum + current_boost + delta
                        # = (prev_prefix_sum + val) + current_boost + delta
                        # = (prev_prefix_sum + current_boost) + val + delta
                        # = current_sum_before + val + delta
                        # But delta = -2*new_min_sum_end
                        # So current_sum_after_flip = new_current_sum_before_flip + delta
                        # which is (current_sum_before + val) + delta
                        # current_sum_after_flip = (new_current_sum_before_flip) + delta
                        # since new_current_sum_before_flip is prefix_sum_prev + val + current_boost_prev
                        # No need to track, because in the next step, the state is tracked by new_prefix_sum and new_current_boost

                        # So, for the next state, new_prefix_sum is prev_prefix_sum + val
                        # new_current_boost is current_boost + delta
                        # Which contributes to the new current_sum = new_prefix_sum + new_current_boost

                        # Now, we add to new_dp:
                        if new_flip_count < new_dp[key_new_prefix].get(new_min_sum_end, float('inf')):
                            new_dp[key_new_prefix][new_min_sum_end] = (new_current_boost, new_flip_count)
        dp = new_dp

    # Now, find the minimal flip_count among all possible states
    min_flips = float('inf')
    for prefix in dp:
        for min_sum in dp[prefix]:
            current_boost, flip_count = dp[prefix][min_sum]
            # Check if the final state is valid
            # The final sum must be prefix + current_boost
            # Also, all intermediate sums were checked, so no need to re-check
            if flip_count < min_flips:
                min_flips = flip_count
    print(min_flips)

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