を から順に検証する解法では、 の最大値が であるため間に合いません。
そこで、 として の最小値を二分探索で求める方法を考えます。
ある の値でドラゴンを討伐出来た時、それ以上の でもドラゴンを討伐出来る事が保証されているためこの解法で解くことが出来ます。
ただし、一つ注意するべき事として の値を仮定した際、 の値次第では、ドラゴンに与えるダメージの合計は、 bit整数におさまらない場合があります。
そのため、 bit整数として扱う場合、ドラゴンに与えるダメージがドラゴンの体力を越えた時点で計算を打ち切る等の工夫が必要です。
C++での実装例は以下の通りです。
xxxxxxxxxx
using namespace std;
int main(){
//入力の読み取り
ll n,d,h;
cin>>n>>d>>h;
vector <ll> a(n);
rep(i,n)cin>>a[i];
//kの範囲を指定
ll kmin=1;
ll kmax=2000000000;
//二分探索を用いて、kの値を仮定し調査する。
while(kmin<kmax){
//kの値を仮定
ll k=(kmax+kmin)/2;
//ダメージを計算
ll dmg=0;
rep(i,n){
dmg+=max((ll)1,a[i]*k-d);
//ダメージを越えた時点で計算を打ち切り。
if(dmg>=h)break;
}
//討伐成功時、最大値を仮定したkの値に更新
//討伐失敗時、最小値をk+1に更新
if(dmg>=h)kmax=k;
else kmin=k+1;
}
cout<<kmin<<endl;
return 0;
}