2023-02-02 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);
}
体調が悪い。
今日のコミット。
- rust-sandbox 1 commit
- rust-atcoder 1 commit