結果

問題 No.3114 0→1
コンテスト
ユーザー みどりむし🦠
提出日時 2025-04-19 10:06:17
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 12 ms / 2,000 ms
コード長 958 bytes
コンパイル時間 3,274 ms
コンパイル使用メモリ 276,344 KB
実行使用メモリ 6,656 KB
最終ジャッジ日時 2025-04-19 10:06:22
合計ジャッジ時間 4,579 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

constexpr long INF64 = 1L << 60;

int main() {
	int n; std::cin >> n;
	std::string s; std::cin >> s;
	
	if(n == 1) {
		std::cout << int(s == "0") << "\n";
		return 0;
	}
	
	int ans = 0;

	std::vector<int> zzl(n), zzr(n), zozl(n), zozr(n);
		
	for(int i : std::views::iota(0, n-1)) {
		if(s[i] == '0' && s[i + 1] == '0') {
			zzl[i]++, zzr[i + 1]++;
		}
	}
	
	for(int i : std::views::iota(0, n-2)) {
		if(s[i] == '0' && s[i + 1] == '1' && s[i + 2] == '0') {
			zozl[i]++, zozr[i + 2]++;
		}
	}

	for(int k : { 2, 1 }) {
		for(int i : std::views::iota(0, n)) {
			if(zzl[i] + zzr[i] + zozl[i] + zozr[i] >= k) {
				++ans;
				s[i] = '1';
				if(zzl[i] > 0 && zzr[i] > 0) {
					zozl[i - 1]++, zozr[i + 1]++;
				}
				if(zzl[i] > 0) zzl[i]--, zzr[i + 1]--;
				if(zzr[i] > 0) zzl[i - 1]--, zzr[i]--;
				if(zozl[i] > 0) zozl[i]--, zozr[i + 2]--;
				if(zozr[i] > 0) zozl[i - 2]--, zozr[i]--;
			}
		}
	}

	std::cout << ans << "\n";
}
0