Codeforces #679 Div1 C. Solo mid Oracle

Narutoが元ネタ？
http://codeforces.com/contest/1434/problem/C

問題

正整数A,B,C,Dに対し、以下のゲームを考える。
モンスターを倒すゲームを考える。
プレイヤーが攻撃すると、敵にAのダメージを与えた後、C秒間の間1秒毎にB体力が回復する。
攻撃は最小D秒毎に行うことができる。
最もダメージを与えた状態に持ち込む場合、そのダメージはいくらか。

解法

回復量B*CよりダメージAが大きければ、いくらでもダメージを与えられる。
以下そうでない場合を考える。
D秒の間にダメージが全回復されてしまうのなら、ダメージを与えた瞬間のAが最大。

そうでない場合、何度か攻撃して止めるのが良い。
そこで攻撃回数を三分探索しよう。

int T;
ll A,B,C,D;

ll hoge(ll t) {
	ll dam=t*A;
	__int128_t sum=t*(t-1)/2;
	sum*=B*D;
	
	if(sum>dam) return -1;
	return dam-sum;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>A>>B>>C>>D;
		
		if(B*C<A) {
			cout<<-1<<endl;
			continue;
		}
		if(C<=D) {
			cout<<A<<endl;
			continue;
		}
		// num attack
		ll att=(C-1)/D;
		ll L=1,R=att+1;
		ll ma=0;
		while(R-L>2) {
			ll m1=(2*L+R)/3;
			ll m2=(2*R+L)/3;
			ll v1=hoge(m1);
			ll v2=hoge(m2);
			ma=max({ma,v1,v2});
			if(v1==-1) {
				R=m1;
			}
			else {
				if(v1<=v2) L=m1;
				if(v2<=v1) R=m2;
			}
		}
		for(i=L;i<=R;i++) ma=max(ma,hoge(i));
		
		
		cout<<ma<<endl;
	}
}

まとめ

なんか問題文が読みにくいな。