普段の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問題の割にコードも割と単純。