2024-05-24

【精進】ABC153 F - Silver Fox vs Monster

毎日自分のレート+400以上のdiffの問題を解きます。
問題リンク F - Silver Fox vs Monster

解法

座標順にソートした後、単純に前から順に「 $X_i$ が負ならcontinue, 正なら座標が $X_i$ から $X_i+2D$ の間にあるモンスターの体力に $H_i$ 以上の最小の $A$ の倍数を引く」という操作を行う。
座標が範囲内にある最大の添字は二分探索、体力の更新は遅延セグメント木を使えば $O(\log N)$ で処理できるので、全体で $O(N\log N)$ となる。

Submission #53801688 - AtCoder Beginner Contest 153

2024-05-23

【精進】ABC046 C - AtCoDeer and Election Report

毎日自分のレート+400以上のdiffの問題を解きます。
問題リンク C - AtCoDeer and Election Report

解法

投票数が満たすべき条件は「広義単調増加」かつ「比が $T_i:A_i$ 」
したがってi回目での投票数は
「 $(i-1)$ 回目の投票数以上の最小の $T_i$ の倍数 $÷T_i$ 」
「 $(i-1)$ 回目の投票数以上の最小の $A_i$ の倍数 $÷A_i$ 」
のうち大きい方を $(i-1)$ 回目の投票数にかければ良い。計算量は $O(N)$
Submission #53756132 - AtCoder Beginner Contest 046

2024-05-21

【精進】ABC073 D - joisino's travel

毎日自分のレート+400以上のdiffの問題を解きます。問題リンク D - joisino's travel

解法

$N\leq200$ という制約からワーシャルフロイド法 $O(N ^ 3)$ が見えてくる。町を訪れる順番は順列全探索で $O(R!)$ 、順番が決まれば移動距離の総和は $O(R)$ で求められるので、合計で $O(N^{3}+R R!)$ となりAC。
Submission #53721947 - AtCoder Beginner Contest 073

2024-05-16

ABC172 C - Tsundoku

問題リンク

C - Tsundoku

解法

答えを二分探索する。
「 $X$ 冊読めるか」の判定は、事前に累積和を取り「机Aの本を $i$ 冊読むための所要時間」(Bも同様)を求めれば、机Aで $i$ 冊、机Bで $(X-i)$ 冊読むとしてそれぞれの所要時間の和が $K$ 以下かどうか判定すれば良い。
判定は $O(1)$ で行うことができ、 $i$ の全探索で $O(N)$ 、答えの範囲は $0$ 以上 $(N+M)$ 以下なので二分探索で $O(\log(N+M))$ 、よって全体の計算量は $O(N\log(N+M))$ となる。