2023-02-20 AGC016 の A を解いた
AGC016 : AtCoder Grand Contest 016 の A を解いた。
- A - Shrinking
https://atcoder.jp/contests/agc016/tasks/agc016_a
- 提出: https://atcoder.jp/contests/agc016/submissions/39071699
- 妙に手こずってしまった
N
が小さいので、'a'..='z'
について単純にシミュレートしても間に合うはずだが、気づかなかった- 提出分では存在する各文字について、各文字の間隔と先頭・末尾の間隔のうち最大のものを求めて (その文字における必要な操作回数) 、その中から最小を選んだ (答え)
use std::iter;
use proconio::{input, marker::Chars};
fn main() {
input! {
s: Chars,
};
let n = s.len();
let mut pos = vec![vec![]; 26];
for (i, c) in s.into_iter().enumerate() {
let index = (c as u8 - b'a') as usize;
pos[index].push(i);
}
let mut count = vec![n; 26];
for (i, p) in pos.into_iter().enumerate() {
if p.is_empty() {
continue;
}
let mut max = 0_usize;
let mut prev = 0_usize;
for p_j in p.into_iter().chain(iter::once(n)) {
let p_j = p_j + 1;
max = max.max(p_j - prev - 1);
prev = p_j;
}
count[i] = max;
}
let ans = count.into_iter().min().unwrap();
println!("{}", ans);
}
今日のコミット。
- rust-atcoder 1 commit
- blog.bouzuya.net 1 commit