ARC150 の A を解いた - bouzuya.hatenablog.com

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" });
    }
}

今日のコミット。

rust-atcoder 1 commit
- arc150 a
node-wsse 4 commits