脳log[20230528]

2023年05月28日 (日) [AtCoder] 精進。昨日あった ABC303-F「Damage over Time」(黄 diff)。昨日は DP とか二分探索とかを考えるも、問題の輪郭、要素同士の関係が十分に掴めなくて解けなかった。一晩(よく寝て)考えた方針はこう。最後のターンから考える。呪文が効果を発揮するターンは１ターン限りなので d が最大の呪文を唱えるのが最善。１ターンで倒せないなら最後から２ターン目を考える。以降３ターン４ターン……。効果ターンが決まっているのでそのターン数で最も効果を発揮する呪文は d でソートして順番に選んでいける。■提出 #41817554 (AC / 539 Byte / 616 ms)。端折った説明は、呪文の効果はターン数に比例して増加した後で一定になるということ。一定になった後の呪文はひとまとめにして最大のものだけを記憶しておけばいい。もうひとつ。ターン数を１ずつ数えることが許されない制約なので、呪文の効果が一定になるタイミングと、比例状態にある呪文の効果とすでに一定になった呪文の効果が逆転するタイミングを捕まえて、飛び飛びに判定をした。ターン数による呪文ダメージの累積と、ターン数の範囲による呪文ダメージの累積の累積をごっちゃにしそうでややこしい。