結果

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

ソースコード

diff # 

def min_operations_to_make_good(s):
    n = len(s)
    s_list = list(s)
    operations = 0
    
    def is_good_string(string):
        prefix_zeros = [0]
        prefix_ones = [0]
        
        for ch in string:
            if ch == '0':
                prefix_zeros.append(prefix_zeros[-1] + 1)
                prefix_ones.append(prefix_ones[-1])
            else:
                prefix_zeros.append(prefix_zeros[-1])
                prefix_ones.append(prefix_ones[-1] + 1)
        
        for i in range(n):
            for j in range(i+1, n):
                if j - i >= 1:
                    zeros = prefix_zeros[j+1] - prefix_zeros[i]
                    ones = prefix_ones[j+1] - prefix_ones[i]
                    if zeros > ones:
                        return False
        return True
    
    if is_good_string(s_list):
        return 0
    
    while not is_good_string(s_list):
        best_pos = -1
        max_improvement = -1
        
        for i in range(n):
            if s_list[i] == '0':
                s_list[i] = '1'
                if is_good_string(s_list):
                    operations += 1
                    return operations
                
                improvement = 0
                for start in range(n):
                    for end in range(start+1, n):
                        if end - start >= 1:
                            zeros = s_list[start:end+1].count('0')
                            ones = s_list[start:end+1].count('1')
                            if zeros <= ones:
                                improvement += 1
                
                s_list[i] = '0'
                
                if improvement > max_improvement:
                    max_improvement = improvement
                    best_pos = i
        
        s_list[best_pos] = '1'
        operations += 1
    
    return operations

test_cases = [
    "01001",
    "1010010001"
]

for s in test_cases:
    print(min_operations_to_make_good(s))
0