結果

問題 No.2145 Segment +-
ユーザー gew1fw
提出日時 2025-06-12 14:34:18
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,746 bytes
コンパイル時間 385 ms
コンパイル使用メモリ 82,596 KB
実行使用メモリ 80,448 KB
最終ジャッジ日時 2025-06-12 14:34:27
合計ジャッジ時間 2,526 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8 WA * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    S = data[1]

    # Check for k=0
    min_sum = 0
    max_sum = 0
    possible = True
    for c in S:
        if c == '+':
            new_min = min_sum + 1
            new_max = max_sum + 1
        elif c == '-':
            new_min = min_sum - 1
            new_max = max_sum - 1
        else:
            new_min = min_sum - 1
            new_max = max_sum + 1

        if new_max < 0:
            possible = False
            break

        new_min = max(new_min, 0)
        min_sum, max_sum = new_min, new_max

    if possible:
        print(0)
        return

    # Check for k=1
    # For each possible split point l (0 <= l <= N), check if it's possible
    # We need to process each possible l in O(1) time. So, precompute two arrays:
    # left: maximum possible sum up to j with s_i=1
    # right: maximum possible sum from j to end with s_i=-1
    left = [0] * (N + 1)
    for i in range(1, N+1):
        c = S[i-1]
        if c == '+':
            add_min = 1
            add_max = 1
        elif c == '-':
            add_min = -1
            add_max = -1
        else:
            add_min = -1
            add_max = 1

        left[i] = left[i-1] + add_max

    right = [0] * (N + 1)
    for i in range(N-1, -1, -1):
        c = S[i]
        if c == '+':
            add = -1  # because s_i = -1
        elif c == '-':
            add = 1
        else:
            add = 1  # choose to add 1 to maximize sum

        right[i] = right[i+1] + add

    for l in range(0, N+1):
        # Compute max possible sum for the split at l
        sum_left = left[l]
        sum_right = right[l]
        total = sum_left + sum_right
        if total < 0:
            continue
        # Check each position up to l, and then after l
        valid = True
        current = 0
        for j in range(1, N+1):
            if j <= l:
                c = S[j-1]
                if c == '+':
                    add = 1
                elif c == '-':
                    add = -1
                else:
                    add = 1  # choose to add 1 to maximize sum
                current += add
            else:
                c = S[j-1]
                if c == '+':
                    add = -1
                elif c == '-':
                    add = 1
                else:
                    add = 1  # choose to add 1 to maximize sum
                current += add
            if current < 0:
                valid = False
                break
        if valid:
            print(1)
            return

    # If k=1 is not possible, answer is 2 (assuming it's possible with two flips)
    print(2)

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