言語アップデート後のRated1発目。
ACL for Pythonなどを使えるようになり、また使える問題も出題されたものの、意外と使っている人は少なかった?
既に、より高機能 or 使い方を熟知してる自前ライブラリを持っている場合は、敢えて使う意味は薄いか。
いろいろ要素があって、何を固定すべきか迷う。
$i$ を固定して考えてみる。
タイプ(お守り番号)ごとに、それまでに出てきたモンスターの攻撃力を集計する。
i 1 2 3 4 5 (Ai,Bi) = (10,3) (20,5) (10,1) (20,3) (20,5) タイプ 2 4 1 3 5 攻撃力の和 0 0 10 30 40
この時、お守りを $K$ 個持っていると、攻撃力の和の、大きい方から $K$ 個分の攻撃を防ぐことができる。
逆に言うと、小さい方から累積和を取っていって、$k$ 個目で累積和が $H$ 以上となったら、 $i$ 体目のモンスターまで倒すには $M-k+1$ 個のお守りが必要ということになる。
タイプ 2 4 1 3 5 攻撃力の和 0 0 10 30 40 累積和 0 0 10 40 80 ↑H=70 だったら i=5体目まで倒すには、1個以上のお守りが必要 ↑H=40 だったら i=5体目まで倒すには、2個以上のお守りが必要
$(i-1 体目まで倒すための必要なお守り数) ~ (i体目まで倒すために必要なお守り数-1)$ の $K$ について、答えは $i-1$ となる。
(実際は、$k$ は $i-1$ の時と $i$ の時で異なっても1個なので、ある $i-1$ が答えとなる $K$ はたかだか1個となる(全て倒せる場合を除き))
$H$ の位置の探索と、状態(タイプ毎の攻撃力の累積和)の更新を効率的に行えるデータ構造は複数あるが、たとえば累積和の二分探索が可能なFenwickTreeを使って実装できる。
モンスター $i$ での更新は、 更新前のタイプ $B_i$ の攻撃力の和を $S$ として、$S$ を示す位置から $S$ を引き、$S+A_i$ を示す箇所に $S+A_i$ を足す、 という2回の $O(\log{N})$ の操作により行える。(個数も同様に、-1,+1で更新できる)
(A6,B6) = (20, 1) 更新前のタイプ1の攻撃力の和S=10 - + FWT上のindex 0 1 2 3 4 0 1 2 3 4 示す攻撃力の和 0 10 20 30 40 → 0 10 20 30 40 FWT_値 0 10 0 30 40 0 0 0 60 40 FWT_個数 2 1 0 1 1 2 0 0 2 1
その後、$H$ で二分探索して必要お守り数を求めるのも $O(\log{N})$ なので、全部で $O(N \log{N})$ で求められる。
2つ以上のタイプで攻撃力の和が被るとき、かつちょうどそこが $H$ の境界になった時、 必要お守り数の計算に注意が必要となる。
FWT上のindex 0 1 2 3 4 示す攻撃力の和 0 10 20 30 40 FWT_値 0 0 0 60 40 FWT_個数 2 0 0 2 1 ↑H=40 のとき、FWT_値 上の二分探索で求まるindexは3
2つ以上のタイプが重なっている場合、その中のいくつかを倒せて、いくつかを倒せない、という事態が発生しうる。
累積和が $H$ 以上になる最初のindex(上例では $i=3$)を二分探索により求めたとき、
このように計算する必要がある。