結果

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

ソースコード

diff # 

def min_operations_to_good_string(N, S):
    a = [1 if c == '1' else -1 for c in S]
    psum = [0] * (N + 1)
    for i in range(N):
        psum[i + 1] = psum[i] + a[i]

    Z = [i + 1 for i, c in enumerate(S) if c == '0']

    def can_make_good(K):
        # 先頭からK個の0を1に変える
        flip = [0] * (N + 2)
        for idx in range(K):
            flip[Z[idx]] += 1
        # 累積和でA[i]を構築
        cnt = 0
        A = [0] * (N + 1)
        for i in range(N + 1):
            if i > 0:
                cnt += flip[i]
            A[i] = psum[i] + 2 * cnt

        min_prefix = A[0]
        for i in range(2, N + 1):
            if A[i] < min_prefix:
                return False
            if A[i - 1] < min_prefix:
                min_prefix = A[i - 1]
        return True

    left, right = 0, len(Z)
    while left < right:
        mid = (left + right) // 2
        if can_make_good(mid):
            right = mid
        else:
            left = mid + 1
    return left
0