bouzuya.hatenablog.com

ぼうずやのにっき

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

今日のコミット。