ABC143 F - Distinct Numbers

問題

atcoder.jp

解法

K枚ずつ食べる時の最大の回数を求めるのではなく、H回食べるときの最大の1回に食べる枚数を求めることにする。

とする。H回食べると決めたとき、同じ数字を同時に食べないように選ぶ1回あたりの食べる枚数は

となる。例えば A = [1,1,1,1,1,2,2,2,3,3,3,4,4,4,5] で4回食べると決めたとき、以下のようにK=3となる。

1st -> 1 2 3 (4)
1nd -> 1 2 3 (5)
3rd -> 1 2 4
4th -> 1 3 4
      (1)

Hを大きい方から計算していくと線形時間で解ける。

コード

use std::cmp;

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let n: usize = sc.read();
    let mut count: Vec<usize> = vec![0; n];
    for _ in 0..n {
        let a = sc.read::<usize>() - 1;
        count[a] += 1;
    }

    count.sort();
    let mut ans = vec![0; n + 1];
    let mut sum = count.iter().sum::<usize>();
    let mut popped = 0;
    for height in (1..(n + 1)).rev() {
        while let Some(c) = count.pop() {
            if c >= height {
                sum -= c;
                popped += 1;
            } else {
                count.push(c);
                break;
            }
        }

        let columns = sum / height + popped;
        ans[columns] = cmp::max(ans[columns], height);
    }
    for k in (0..n).rev() {
        ans[k] = cmp::max(ans[k], ans[k + 1]);
    }

    for k in 1..(n + 1) {
        println!("{}", ans[k]);
    }
}

pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n')
            .take_while(|&b| b != b' ' && b != b'\n')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}