bouzuya/nostr-keyconv を Docker 経由で利用できるようにした。
昨日はなぜか docker push しても 5xx エラーが返される状態だったので。
ABC153 : AtCoder Beginner Contest 153 の A, B, C, D, E, F を解いた。
- A - Serval vs Monster
https://atcoder.jp/contests/abc153/tasks/abc153_a
- 提出: https://atcoder.jp/contests/abc153/submissions/39357283
(h + a - 1) / a
- B - Common Raccoon vs Monster
https://atcoder.jp/contests/abc153/tasks/abc153_b
- 提出: https://atcoder.jp/contests/abc153/submissions/39357305
h <= a.into_iter().sum::<usize>()
- C - Fennec vs Monster
https://atcoder.jp/contests/abc153/tasks/abc153_c
- 提出: https://atcoder.jp/contests/abc153/submissions/39357605
- H を降順にソートして先頭 K 個をスキップした和が攻撃の回数になる
- D - Caracal vs Monster
https://atcoder.jp/contests/abc153/tasks/abc153_d
- 提出: https://atcoder.jp/contests/abc153/submissions/39357782
- 再帰的に求めれば良い、念のためでメモ化再帰にしたけど要らなかったかも……
- E - Crested Ibis vs Monster
https://atcoder.jp/contests/abc153/tasks/abc153_e
- 提出: https://atcoder.jp/contests/abc153/submissions/39358234
DP[i] := 体力を i 減らすのに必要な魔力の最小値
とおくDP[0] = 0
から体力を 1 ずつ、魔法を走査して配る DP で解いた- 体力を i にするのに必要な魔力の最小値とおく (減らす) 方が自然な感じがしたけど、うまく遷移できなさそうだったのでこちらにした
- F - Silver Fox vs Monster
https://atcoder.jp/contests/abc153/tasks/abc153_f
- 提出: https://atcoder.jp/contests/abc153/submissions/39359497
- 左側にギリギリ当たる位置で爆弾を使っていく貪欲法で良い
- 位置 (区間) ごとの爆弾の使用回数 (≒ダメージ) は、いもす法的に持てば良い
- ただ
X_i <= 10^9
なのでX_i
で持つことはできない - 減らす要素を二分探索 (
X_i + 2 * D
) で検索して決めて、そこまで維持されるようにすれば良い (ある種の座標圧縮)
use proconio::input; use superslice::Ext; fn main() { input! { n: usize, d: usize, a: usize, mut xh: [(usize, usize); n], }; xh.sort(); let mut counts = vec![0_usize; xh.len() + 1]; let mut count = 0_usize; for (i, (x, h)) in xh.iter().copied().enumerate() { count -= counts[i]; if count * a < h { let c = ((h - (count * a)) + a - 1) / a; count += c; counts[xh.upper_bound_by_key(&(x + 2 * d), |(x, _)| *x)] += c; } } println!("{}", counts.iter().sum::<usize>()); }
今日のコミット。
- rust-sandbox 2 commits
- rust-atcoder 1 commit
- bouzuya.net 1 commit
- nostr-keyconv 1 commit