結果

問題 No.3114 0→1
ユーザー h tsuneki
提出日時 2025-04-19 00:17:09
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 1,124 bytes
コンパイル時間 180 ms
コンパイル使用メモリ 11,776 KB
実行使用メモリ 10,624 KB
最終ジャッジ日時 2025-04-19 00:17:12
合計ジャッジ時間 2,290 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other WA * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

def min_operations(n, s):
    """
    For a good string, any substring must have count(0) <= count(1).
    
    Key insight: To ensure all substrings have this property, we need to ensure
    that each position's running balance (count(1) - count(0)) never goes below
    the minimum balance seen so far minus 1.
    
    We use a greedy approach: When we encounter a position that violates this rule,
    we need to convert enough 0s to 1s to fix the balance.
    """
    balance = 0  # Current balance: count(1) - count(0)
    operations = 0  # Total operations needed
    
    for char in s:
        # Update balance
        if char == '1':
            balance += 1
        else:  # char == '0'
            balance -= 1
        
        # If balance becomes negative, we need to convert some 0s to 1s
        if balance < 0:
            operations += abs(balance)  # Convert enough 0s to make balance 0
            balance = 0  # After conversion, balance becomes 0
    
    return operations

def main():
    n = int(input())
    s = input().strip()
    print(min_operations(n, s))

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