typical90-06

AtCoder
Programming
Author

Serika Yuzuki

Published

October 23, 2023

問題リンク

概要

失敗した解き方

コメントの中でやった通りのやり方。これだと計算量が \(k^{n}\) になってしまうためにデカいテストデータでは通らなかった。

use proconio::input;

fn main() {
    input! {
        n: usize,
        k: usize,
        s: String,
    }

    let vec_str = s.chars().into_iter().collect::<Vec<char>>();
    let mut vec_str_to_usize = vec_str
        .clone()
        .into_iter()
        .map(|c| c.to_digit(36).unwrap() as usize)
        .collect::<Vec<usize>>();

    // 例えば、n=7, k=3, s=abcdefgの場合、
    // 0,1,2,3,4=n-k の中から最大のものを選んで、で残ったやつから i,i+1,...,n-k+1=3 の中から最大のものを選ぶ。
    // これから続けて、

    let mut ans = vec![];

    // let first_index = find_biggest_index(vec_str_to_usize.clone(), 0, n - k);
    // ans.push(vec_str[first_index]);
    // let second_index = find_biggest_index(vec_str_to_usize.clone(), first_index + 1, n - k + 1);

    let mut now_index = 0;
    for i in 0..k {
        if i == 0 {
            now_index = find_smallest_index(vec_str_to_usize.clone(), 0, n - k);
        } else {
            now_index = find_smallest_index(vec_str_to_usize.clone(), now_index + 1, n - k + i);
        }
        ans.push(vec_str[now_index]);
    }

    println!("{}", ans.into_iter().collect::<String>());
}

fn find_smallest_index(
    vec_str_to_usize: Vec<usize>,
    start_index: usize,
    end_index: usize,
) -> usize {
    let mut min = 36;
    let mut index = 0;

    for i in start_index..end_index + 1 {
        if min > vec_str_to_usize[i as usize] {
            min = vec_str_to_usize[i as usize];
            index = i;
        }
    }

    index
}

なので別の方法を考える。

\(N\) の長さの文字列の中から一番でかいアルファベットを探して、それが \(N-K\) 番目より前にあればOK。その値を上から順に並べていく。これだと計算量は \(NK\) になる。けどまだダメ。

fn find_smallest_index(vec_str_to_usize: Vec<usize>, limit_index: usize) -> usize {
    for (i, j) in iproduct!(11..36, 0..limit_index) {
        if vec_str_to_usize[j] == i {
            return j;
        }
    }
    0
}

ここで問題となるのが、 \(\symscr{O}(10^8)\) がおおよそ実行時間が2秒であることを考慮すると、 \(NK\) だとダメだということ。なので \(N\) か \(K\) を \(1\) にするような方法を考えたとき、Stringを整理して、 \(N\) 回の計算を終えたらすぐに \(K\) 回の計算をすれば終わるようなデータベースを準備すればいい。これだと計算量は \(N+K\) になるので、解決できる。

use proconio::input;

fn main() {
    input! {
        n: usize,
        k: usize,
        s: String,
    }

    let vec_str = s.chars().into_iter().collect::<Vec<char>>();
    let mut vec_str_to_usize = vec_str
        .clone()
        .into_iter()
        .map(|c| c.to_digit(36).unwrap() as usize - 10)
        .collect::<Vec<usize>>();

    let mut ans = vec![];

    let r = generate_r(vec_str_to_usize.clone());

    let mut position = -1;

    for i in 0..k {
        for j in 0..26 {
            let tmp = r[(position + 1) as usize][j];
            if tmp != -1 && n - tmp as usize >= k - i {
                ans.push(char::from_digit((j + 10) as u32, 36).unwrap());
                position = tmp as isize;
                break;
            }
        }
    }

    println!("{}", ans.into_iter().collect::<String>());
}

// r[i][j]がi桁目の数より右側にjが出現する最小のインデックスを返す

fn generate_r(vec_str_to_usize: Vec<usize>) -> Vec<Vec<isize>> {
    let mut r: Vec<Vec<isize>> = vec![vec![-1; 26]; vec_str_to_usize.len() + 1];

    for i in (0..vec_str_to_usize.len()).rev() {
        for j in 0..26 {
            if vec_str_to_usize[i] == j {
                r[i][j] = i as isize;
            } else {
                r[i][j] = r[i + 1][j];
            }
        }
    }

    r
}

困難は分割せよっていう話があるが、これは困難を積集合として分割してはならないという教訓を与えてくれた。

発見

実行時間の目安

\(\symscr{O}(10^8)\) がおおよそ実行時間が2秒である。これが大体どのコンテストでもリミッターになってるらしい。

問題

問題点

Back to top