2023-02-15 ARC150 の A を解いた
ARC150 : AtCoder Regular Contest 150 の A を解いた。
- A - Continuous 1
https://atcoder.jp/contests/arc150/tasks/arc150_a
- 提出: https://atcoder.jp/contests/arc150/submissions/38907959
- 解説 AC
'?'の数に気をとられたのだけど、K個の範囲の1の数と0の数で判定できた'0'の数が0で'1'がその範囲にすべて含まれていれば他の範囲を調べる必要がないK個の範囲内の'1'と'0'の数の増減はそれぞれ 1 個ずつなのでO(1)で計算できて全体としてO(N)になる
use proconio::{input, marker::Chars};
fn main() {
input! {
t: usize,
};
for _ in 0..t {
input! {
_n: usize,
k: usize,
s: Chars,
}
let count1 = s.iter().copied().filter(|s_i| s_i == &'1').count();
let mut count = 0_usize;
let mut c0 = 0_usize;
let mut c1 = 0_usize;
for s_i in s.iter().copied().take(k) {
match s_i {
'0' => c0 += 1,
'1' => c1 += 1,
'?' => {}
_ => unreachable!(),
}
}
count += if c0 == 0 && c1 == count1 { 1 } else { 0 };
for (i, s_i) in s.iter().copied().enumerate().skip(k) {
match s_i {
'0' => c0 += 1,
'1' => c1 += 1,
'?' => {}
_ => unreachable!(),
}
match s[i - k] {
'0' => c0 -= 1,
'1' => c1 -= 1,
'?' => {}
_ => unreachable!(),
}
count += if c0 == 0 && c1 == count1 { 1 } else { 0 };
}
let ans = count == 1;
println!("{}", if ans { "Yes" } else { "No" });
}
}
今日のコミット。