結果

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

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
using namespace std;

void toBitarray(const string& s, vector<bool>& S, int k, int fullN) {
    for (int i = 0; i < k - 1; i++) {
        S[i] = true;
    }

    for (int i = k - 1; i < fullN; i++) {
        S[i] = (s[i - k + 1] == '1') ? true : false;
    }
}

int min_find(const string& s, int N, int n) {
    const int weight_min = (n + 1) / 2;
    const int fullN = N + weight_min - 1;
    int change = 0;
    int H_weight = 0;
    vector<bool> S(fullN);
    vector<bool> K(fullN);

    toBitarray(s, S, weight_min, fullN);

    copy(S.begin(), S.end(), K.begin());

    for (int i = 0; i < n; i++) {
        H_weight = H_weight + (S[i] ? 1 : 0);
    }

    if (H_weight < weight_min) {
        S[n - 1] = true;
        H_weight++;
        change++;
    }

    for (int i = 1; i < fullN - n + 1; i++) {
        H_weight = H_weight - (S[i - 1] ? 1 : 0);
        H_weight = H_weight + (S[i + n - 1] ? 1 : 0);
        if (H_weight < weight_min) {
            S[i + n - 1] = true;
            H_weight++;
            change++;
        }
    }

    return change;
}

int main() {
    int N;
    string s;
    cin >> N >> s;
    cout << min_find(s, N, 3) << endl;
    return 0;
}
0