ひな人形 / PAST #16 I

ひな人形を片付けた。毎年文句を言いながら片付けている。

---

第16回 アルゴリズム実技検定(過去問)

• I - アメ https://atcoder.jp/contests/past16-open/tasks/past202309_i
  • 提出: <>
  • 解説 AC
  • じっくり考えれば解けたかも……。
  • M <= 10^12 なので単純に試行はできない
  • ある程度までは一気に進める方法を考えないといけない
  • 二分探索で M 回の操作が終了したときの子どもの持っているアメの最小個数を探せる
  • 最小個数以上になるよう更新すれば、あとは最大でも N 人に 1 回ずつで済むので残りを単純にシミュレートすればいい

use std::{cmp::Reverse, collections::BinaryHeap};

use proconio::input;

fn main() {
    input! {
        n: usize,
        m: usize,
        k: usize,
        a: [usize; n],
    };
    let mut ok = 0_usize;
    let mut ng = 1 << 60;
    while ng - ok > 1 {
        let mid = (ok + ng) / 2;
        let mut sum = 0_usize;
        for a_i in a.iter().copied() {
            if a_i < mid {
                sum += (mid - a_i + k - 1) / k;
            }
        }
        if sum <= m {
            ok = mid;
        } else {
            ng = mid;
        }
    }

    let min = ok;
    let mut count = 0_usize;
    let mut b = a.clone();
    for b_i in b.iter_mut() {
        if *b_i < min {
            let c = (min - *b_i + k - 1) / k;
            count += c;
            *b_i += c * k;
        }
    }

    let mut pq = BinaryHeap::new();
    for (i, b_i) in b.iter().copied().enumerate() {
        pq.push(Reverse((b_i, i)));
    }

    for _ in 0..m - count {
        let Reverse((b_i, i)) = pq.pop().unwrap();
        pq.push(Reverse((b_i + k, i)));
    }

    let mut ans = vec![0; n];
    for Reverse((b_i, i)) in pq {
        ans[i] = b_i;
    }
    for a in ans {
        println!("{}", a);
    }
}

---

今日のコミット。

• rust-atcoder 1 commit
  • past16-open i