bouzuya.hatenablog.com

ぼうずやのにっき

Tenka1 Programmer Contest 2019 の C を解いた

Tenka1 Programmer Contest 2019 の C を解いた。

  • C - Stones https://atcoder.jp/contests/tenka1-2019/tasks/tenka1_2019_c
    • 提出: https://atcoder.jp/contests/tenka1-2019/submissions/38550382
    • ...### のように右側に # を寄せた形をつくれば良い
    • ...... のように # がなかったり ###### のように . がなくても良い
    • 操作後の形を ######, .#####, ..####, ... ...... としたとき何回の操作が必要かを調べれば良い
    • 左端からの # の個数の累積和と右端からの . の個数の累積和があれば O(1) で計算できる
    • 操作後の形が N 種類あるので全体で O(N) になる
    • いろいろ間違えて 2WA
use proconio::{input, marker::Chars};

fn main() {
    input! {
        n: usize,
        s: Chars
    };

    let mut ans = n;
    let mut w = vec![0_usize; n];
    let mut b = vec![0_usize; n];

    let mut count = 0_usize;
    for i in (0..n).rev() {
        if s[i] == '.' {
            count += 1;
        }
        w[i] = count;
    }
    if count == n {
        ans = 0;
    }

    let mut count = 0_usize;
    for i in 0..n {
        if s[i] == '#' {
            count += 1;
        }
        b[i] = count;
    }
    if count == n {
        ans = 0;
    }

    let ans = ans.min(w[0]).min(b[n - 1]).min(
        (0..n)
            .map(|i| w[i] + if i > 0 { b[i - 1] } else { 0 })
            .min()
            .unwrap(),
    );
    println!("{}", ans);
}

体調が悪い。

今日のコミット。