htkb-proconの日記

初心者がPythonで問題解いた記録

AtCoder Regular Contest 075 参戦記

o— 1281 -> 1293

C: Bugged - AtCoder Regular Contest 075 | AtCoder

結果:AC
Submission #1323396 - AtCoder Regular Contest 075 | AtCoder

数列をソートして合計を取り10の倍数だったら数列の中の10の倍数ではない最小の数字を捨てて合計をチェック……を繰り返した。←これ今思えば繰り返す必要なかった(10の倍数から非10の倍数引けば非10の倍数になることは自明なので)

D: Widespread - AtCoder Regular Contest 075 | AtCoder

結果:わかんなかった

ソートした数列を取り出したり泥臭いやり方をしようとしてた時点で負けだった。てかにぶたんなんて全く思いつかなかったよ……!

Tターンで全滅させられる、とは、各モンスターに対してT*B+(A-B)*nn(切り上げ)の合計を求め、それがT以下であるということ。(A-B)*nとは何度そのモンスターを中心にして攻撃したかということなので。

A = 3, B = 1
h = [3, 3, 9] 

T = 3 とすると、
h1: 3 = 3*1+(3-1)*n
    3 = 3 + 2n
    n = 0 # 3ターン全て中心に選ばなくても倒せる
h2: 同上
h3: 9 = 3*1+(3-1)*n
    9 = 3 + 2n
    n = 3 # 3ターン中心に選べば倒せる

T >= nの合計 より、3ターン以内で倒せた

以上の考え方で、Tの値を二分探索する。
ACコード:Submission #1329512 - AtCoder Regular Contest 075 | AtCoder
pythonだと1787msもかかってるんだけどやり方悪いのかな……?