Codeforces #299 Div1 A. Tavas and Karafs

CF299に参加。
ABと2完だけだったけど、Cの正答率が低かったこともあり、3Hackも活きてレート上昇。
http://codeforces.com/contest/536/problem/A

問題

正整数A,Bが与えられるとき、数列S[i]=A+(i-1)*Bと定義する。
m-biteとは、数列のうち異なるm個以下の要素を1減らす処理の事を言う。

ここでN個のクエリが与えられる。
各クエリはパラメータ(L,T,M)からなる。
部分列S[L..R]をM-biteをT回以下ですべて0に出来る、という最大のRを答えよ。

解法

S[L]＞Tの時は最小値であるS[L]すら0に出来ないので、条件を満たすRはない。

あとは二分探索で条件を満たすRを絞り込んでいく。
S[L..R]がM-bite T回以内で0に出来るのは、以下の両条件を満たした場合である。

• S[R]≦T
• sum(S[L..R])≦T*M

1回のM-biteでS[L..R]の残りの値のうち大きい順にM個選んで1減算する、という手順を繰り返せば上記２条件で題意を満たせることが確認できる。

ll A,B,N;
ll L,T,M;

bool ok(ll R) {
	ll ma=A+(R-1)*B;
	ll mi=A+(L-1)*B;
	ll D=R-L;
	
	if(ma>T) return false;
	return (mi*(D+1)+B*D*(D+1)/2) <= T*M;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B>>N;
	
	while(N--) {
		cin>>L>>T>>M;
		ll mi=A+(L-1)*B;
		ll R=L;
		if(mi>T) {
			R=-1;
		}
		else {
			for(i=20;i>=0;i--) if(ok(R+(1LL<<i))) R+=1LL<<i;
		}
		cout<<R<<endl;
	}
}

まとめ

二分探索に発想が至れば後は簡単。