kmjp's blog

競技プログラミング参加記です

Codeforces #1133 : Div.1 C. Anti-Productive

普段のCより易しいと思ったけど1250ptだったか。
https://codeforces.com/contest/2279/problem/C

問題

整数列Aが与えられる。
各要素を任意回数デクリメントし、どの2要素の積もL未満となるようにしたい。
最小何回デクリメントすべきか。

解法

以下を両方試した。

  • 全要素を√L未満にする
  • 最大要素以外をa以下にした時、最大要素をL/a未満にする。これをaを√L程度まで総当たりする。
int T,N;
ll L,A[505050];
ll S[505050];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>L;
		int s=0;
		while((s+1)*(s+1)<L) s++;
		ll ret=0;
		FOR(i,N) {
			cin>>A[i];
			if(A[i]>s) ret+=A[i]-s;
		}
		sort(A,A+N);
		FOR(i,N) S[i+1]=S[i]+A[i];
		
		ret=min(ret,S[N-1]);
		//全部ルート以下
		int lef=0;
		for(x=1;x*x<L;x++) {
			
			y=L/x;
			if(x*y==L) y--;
			ll sum=max(0LL,A[N-1]-y);
			while(lef<N-1&&A[lef]<=x) lef++;
			ll sum2=(S[N-1]-S[lef])-1LL*(N-1-lef)*x;
			ret=min(ret,sum+sum2);
		}
		
		
		cout<<ret<<endl;
		
	}
}

まとめ

C問題の割にコードも割と単純。