2023-02-10 AGC011 の A, B を解いた
AGC011 : AtCoder Grand Contest 011 の A, B を解いた。
- A - Airport Bus
https://atcoder.jp/contests/agc011/tasks/agc011_a
- 提出: https://atcoder.jp/contests/agc011/submissions/38758997
- t は昇順にソートして良い
- 貪欲に人数の上限
Cまたは時刻の上限T_i + Kまで走査を進める - 進めた回数だけバスが必要になる
- B - Colorful Creatures
https://atcoder.jp/contests/agc011/tasks/agc011_b
- 提出: https://atcoder.jp/contests/agc011/submissions/38760118
- A は昇順にソートして良い
- A_N はすべて食べられるので当然残った生き物の色に含まれる
- A_{N-1} が A_N を食べられるかは A_{N-1} よりも小さいものをすべて食べた上で 2 倍したものが A_N に届いていれば良い
- 残りは同様に判断できる
- A_i より小さいものをすべて食べたときの大きさは累積和で求められる
- もっとも右側の食べられるところを調べれば答えが求められる (rposition なので判定がややこしい)
use proconio::input;
fn main() {
input! {
n: usize,
mut a: [usize; n],
};
a.sort();
let c = std::iter::once(0)
.chain(a.iter().scan(0, |acc, &i| {
*acc += i;
Some(*acc)
}))
.collect::<Vec<usize>>();
let count = a
.into_iter()
.zip(c.into_iter())
.rposition(|(a_i, c_i)| a_i > c_i * 2)
.unwrap_or(0);
let ans = n - count;
println!("{}", ans);
}
育児。下の子が「てんてんどんどんてんてんどんどん」と天丼マンの歌を歌う。ちょっとだけ間違っている。
今日のコミット。
- rust-sandbox 2 commits
- rust-atcoder 1 commit