結果

問題 No.3114 0→1
コンテスト
ユーザー aaaaaaaaaaa
提出日時 2025-04-18 23:04:23
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 4,087 bytes
コンパイル時間 648 ms
コンパイル使用メモリ 74,176 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-04-18 23:04:25
合計ジャッジ時間 1,400 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int N;
    std::cin >> N;
    std::string S;
    std::cin >> S;

    // B[k] represents the balance (count of 1s minus count of 0s) of the prefix S_new[0...k]
    // B[-1] is defined as 0.
    // We need B[j] - B[i-1] >= 0 for all 0 <= i <= j < N with j-i+1 >= 2.
    // This is equivalent to B[k] >= B[m] for all -1 <= m <= k-2 and 0 <= k < N.
    // So, for k = 1, ..., N-1, we need B[k] >= max(B[-1], B[0], ..., B[k-2]).

    long long achieved_b_prev = 0; // Represents B_{i-1} in the iteration for index i
    long long changes = 0;

    // This variable will store max(B[-1], B[0], ..., B[i-2]) as we iterate through index i.
    // It is needed to check the condition for B[i].
    long long max_b_up_to_prev_minus_2 = 0; // max(B[-1]) = 0, needed for i=1 check

    for (int i = 0; i < N; ++i) {
        char current_char = S[i];
        int char_val = (current_char == '1') ? 1 : -1;

        // Calculate the required minimum value for B[i]
        long long required_b_i;
        if (i == 0) {
            // For substrings of length >= 2 ending at index 0, there are none.
            // The condition B[k] >= max(B[-1], ..., B[k-2]) applies for k >= 1.
            // B[0] has no constraint relative to previous terms via this rule.
            // However, the general form count(0) <= count(1) for length >= 2 still implies constraints.
            // The specific condition is that for any substring Y, count(0 in Y) <= count(1 in Y).
            // For k=0, only substring ending here is S[0] (length 1), no condition.
            required_b_i = -2e18; // Effectively no lower bound for B[0] from this rule
        } else if (i == 1) {
            // For substrings ending at index 1 of length >= 2, only S[0...1].
            // Condition: B[1] - B[-1] >= 0. So B[1] >= B[-1] = 0.
            required_b_i = 0;
        } else {
            // For i >= 2, substrings ending at i of length >= 2 are S[0...i], S[1...i], ..., S[i-2...i].
            // Conditions: B[i] >= B[-1], B[i] >= B[0], ..., B[i] >= B[i-2].
            // So B[i] >= max(B[-1], B[0], ..., B[i-2]).
            required_b_i = max_b_up_to_prev_minus_2;
        }

        // Calculate the potential value of B[i] if we keep S[i] as its original value (or if it's '1')
        long long potential_b_i = achieved_b_prev + char_val;

        long long achieved_b_i;
        if (potential_b_i >= required_b_i) {
            // If keeping the original value satisfies the condition, do so.
            achieved_b_i = potential_b_i;
        } else {
            // If keeping the original '0' makes B[i] too low, we must change S[i] from '0' to '1'.
            // This increases the value by 2 compared to decreasing by 1.
            // The value becomes B_{i-1} + 1. This is only possible if S[i] was '0'.
            // If S[i] was '1', potential_b_i = B_{i-1} + 1. If this is < required, previous choices were wrong or impossible?
            // The problem constraints and form suggest a solution exists.
            // When potential_b_i < required_b_i, it must be that S[i] is '0'.
            achieved_b_i = achieved_b_prev + 1; // Change '0' to '1'
            changes++;
        }

        // Update max_b_up_to_prev_minus_2 for the next iteration (i+1).
        // The next iteration needs max(B[-1], ..., B[i-1]).
        // This is max(current max_b_up_to_prev_minus_2, B[i-1]).
        // B[i-1] is the achieved_b_prev from *this* iteration's perspective.
        if (i >= 1) { // We need B_{i-1} to update max for next step (i+1).
             // max(B_{-1}..i-2, B_{i-1})
             max_b_up_to_prev_minus_2 = std::max(max_b_up_to_prev_minus_2, achieved_b_prev);
        }
        // For i=0, achieved_b_prev is B[-1]=0. max_b_up_to_prev_minus_2 remains 0 for i=1.

        // Update achieved_b_prev for the next iteration.
        achieved_b_prev = achieved_b_i;
    }

    std::cout << changes << std::endl;

    return 0;
}
0