ABC023 D 射撃王

Submission #2437277 - AtCoder Beginner Contest 023

所見

二分探索はすぐに思いつくことができるが、高速にスコアPを達成できるかどうかを判定するのが難しかった。ここを典型として処理できるのが上手い人なんだろうと思う。とはいえ、解説を見ずに思いつけたのは成長を感じる。

問題概要

N個の風船があり、一秒に1つの風船を割れるとき、風船を割った高さの最大値がそのスコアとなるゲームをする。N個の風船の高さの初期値H_iと1秒に上昇する速度S_iが与えられるとき、得られるスコアの最小値を求めよ。

取った方針

あるスコアPでクリアできるかどうかを考えたとき、一定以下ではクリアできず、それより大きい場合はクリアできるということは容易に考えられるので「クリアできるかどうかで二分探索」が方針として考えられる。
その方針を取るとき、O(N)でクリアできるかどうかを判定できれば、O(NlogSN)で間に合うことがわかる。
頑張って考えると、「スコアPでクリアするためにその風船を何秒以内で割らなければいけないか」を(score-H[i])/S[i]で求めることができ、それをソートしてi番目の値がiを超えていなければOKだということがわかる。(i番目の風船は0-originでi秒目に割ることになるため)
これで、O(NlogN)でスコアPでクリアできるかどうかを判定できるので、二分探索と合わせてO(NlogNlogSN)となり間に合う。

正しい方針

同上

得られた知見

・「できる/できないの境界がある場合のスコアの最大/最小値」を求める場合、できるかできないかで二分探索をする。

解くのに必要な要素

・判定関数を作るタイプの二分探索
・ソート
・貪欲法 (早く目標スコアを超えてしまう風船を優先的に割る)

周辺調査によって得られた知見

特になし