結果

問題 No.3114 0→1
コンテスト
ユーザー Naru820
提出日時 2025-05-21 15:48:14
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,278 bytes
コンパイル時間 526 ms
コンパイル使用メモリ 82,440 KB
実行使用メモリ 82,160 KB
最終ジャッジ日時 2025-05-21 15:48:18
合計ジャッジ時間 4,759 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other WA * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def solve():
    N = int(input())
    S = input()

    current_balance = 0
    operations = 0
    min_heap_for_zeros = []

    for i in range(N):
        if S[i] == '1':
            current_balance += 1
        else: # S[i] == '0'
            # '0' を '1' に変更する可能性を考慮し、現在の balance をヒープに追加
            # ヒープには、'0' が追加された時点での current_balance を格納する。
            # '0' が `current_balance` を -1 させる前の値。
            # heapq は最小ヒープなので、負の値として格納することで最大ヒープのように振る舞う。
            heapq.heappush(min_heap_for_zeros, current_balance)
            current_balance -= 1
        
        # current_balance が負になった場合、修正が必要
        if current_balance < 0:
            # 修正操作として、最も「負の度合いが強い」0 を 1 に変更する
            operations += 1
            # ヒープから最小値（最も負の度合いが強い balance）を取り出す
            heapq.heappop(min_heap_for_zeros)
            # 0 を 1 に変更することで、current_balance は 2 増加する
            current_balance += 2

    print(operations)

solve()
0