競プロ典型 006

https://atcoder.jp/contests/typical90/tasks/typical90_e

入力例1で考えると、aを頭から探して、aが一つあるので、その次からbを探して、無いのでcを探して、と最後にたどり着くまで繰り返します。アルファベットを整数に直すと書きやすいです。

// Smallest Subsequence
#![allow(non_snake_case)]

use std::collections::{BTreeSet, BTreeMap};


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// process ////////////////////

fn read_input() -> (usize, String) {
    let v = read_vec();
    let K = v[1];
    let S = read();
    (K, S)
}

fn make_converter(v: &Vec<usize>) -> BTreeMap<usize, usize> {
    let s: BTreeSet<usize> = v.iter().map(|&n| n).collect();
    s.iter().enumerate().map(|(i, &n)| (n, i)).collect::<BTreeMap<_, _>>()
}

fn convert(v1: Vec<usize>, dic: &BTreeMap<usize, usize>) -> Vec<usize> {
    v1.into_iter().map(|n| *dic.get(&n).unwrap()).collect::<Vec<_>>()
}

fn classify(v: &Vec<usize>) -> Vec<Vec<usize>> {
    let n = v.iter().map(|&e| e).max().unwrap();
    let mut f: Vec<Vec<usize>> = vec![vec![]; n+1];
    for (p, &e) in v.iter().enumerate() {
        f[e].push(p)
    }
    f
}

fn find_first(p: usize, q: usize, f: &[usize]) -> Option<usize> {
    if f.len() <= 2 {
        return f.iter().enumerate().filter(|(_, &pos)| p <= pos && pos < q).
                                                        map(|(j, _)| j).next()
    }
    
    let mid = f.len() / 2;
    if f[mid] < p {
        find_first(p, q, &f[mid+1..])
    }
    else {
        find_first(p, q, &f[..mid+1])
    }
}

fn add_char(p: usize, q: usize, f: &Vec<usize>) -> Option<usize> {
    if let Some(j) = find_first(p, q, &f[..]) {
        Some(f[j]+1)
    }
    else {
        None
    }
}

fn decode(v: &Vec<usize>, dic: &BTreeMap<usize, usize>) -> String {
    let rev_dic: BTreeMap<usize, usize>
                    = dic.iter().map(|(k, v)| (*v, *k)).collect();
    v.iter().map(|n| rev_dic.get(n).unwrap()).
                map(|&m| (m as u8) as char).collect::<String>()
}

fn F(K: usize, S: String) -> String {
    let L = S.len();
    let v1: Vec<usize> = S.chars().map(|c| c as usize).collect();
    let dic = make_converter(&v1);
    let v2 = convert(v1, &dic);
    let freq = classify(&v2);
    
    let mut v3: Vec<usize> = vec![];
    let mut p: usize = 0;
    for _ in 0..K {
        for (i, f) in freq.iter().enumerate() {
            if let Some(q) = add_char(p, L-K+v3.len()+1, f) {
                p = q;
                v3.push(i);
                break
            }
        }
    }
    decode(&v3, &dic)
}

fn main() {
    let (K, S) = read_input();
    println!("{}", F(K, S))
}