こんにちは。なんだか風邪気味でちょっと厳しいとーです。
AGC002B
箱がN個あり、赤いボールが1つ、白いボールがN-1個入ってる これを与えられた操作でボールを移す作業をしたとき、赤いボールが入っている可能性のある箱はいくつありますか、という問題
最初に、ボールの数と、赤いボールが入っている可能性があるかどうかの二つのリストを持っておく、そして
①移す側の箱に赤いボールが入っている可能性がある→移される側も赤いボールが入る可能性がある（その逆もしかり）
②移す側の箱のボールの数を-1、移される側の箱のボールの数を+1する
③移す側の箱のボールの数が、操作終了後に0になったら、その箱には赤いボールが入っている可能性はないので、この部分を変更する
という操作を続ける
ABC063D
モンスターN体に対し、1体にはA,N-1体にはBのダメージが与えられる魔法を最低で何回唱えればモンスターが全部倒せますか、という問題
T回でこれが全部終わると仮定すると、この施行は
①体力がB*Tより多いモンスターに対し、そのモンスターの体力をSとして、体力をS-B*Tまで削った後、A-Bのダメージを何回か与えることと等価
②体力がB*Tより少ないモンスターには追加でダメージを与える必要がない
ということなので、①で求めた追加ダメージの回数がTと等しくなるところを探してあげればよい
二分探索を使えば、上限を(モンスターの体力合計)/B、下限を-1としたうえで、上限-下限が1より大きい間は、
T = （上限+下限）//2
として、追加ダメージの回数をO(N)で求めたあと、それがTを上回っていたら、追加ダメージが想定より多く必要になってしまっているので、下限をTにあわせる、逆にTを下回っていたら、上限をTに合わせる、ということを繰り返していく
atcoder.jp
（実行時間ギリギリ......）
