Codeforces ECR #146 : D. Balancing Weapons

4問目から割と難しい回。
https://codeforces.com/contest/1814/problem/D

問題

N個の銃があり、それぞれ発射間隔F[i]と1発あたりのダメージD[i]が与えられる。
銃の威力P[i]は、P[i]=F[i]*D[i]として計算できる。

Dを変更し、Pの最大値と最小値の差がK以下となるようにしたい。
ただし、変更後のDは正整数でなければならない。

Dを書き換えないといけない銃の数の最小値を求めよ。

解法

全部書き換えれば条件を満たせる。
あとは解がN未満のケースを考えよう。
この場合1つはDを変更しないので、そのような銃iを考えると、他の銃の威力は[P[i]-K,P[i]+K]の範囲になければならない。
尺取り法の要領で、このうち長さKの区間に全銃の威力を入れられるか、またその時のDを変更すべき数を数えよう。

int T;
int N,K;
int F[3030],D[3030];
int num[2020];
int dp[3030];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		ZERO(num);
		FOR(i,N) {
			cin>>F[i];
			num[F[i]]++;
		}
		vector<ll> P;
		FOR(i,N) {
			cin>>D[i];
			P.push_back(1LL*F[i]*D[i]);
		}
		sort(ALL(P));
		int mi=N;
		FOR(i,N) {
			ll L=max(1LL,1LL*F[i]*D[i]-K);
			ll R=1LL*F[i]*D[i];
			ZERO(dp);
			for(j=1;j<=2000;j++) {
				int n=num[j];
				if(j<=K+1) {
					dp[0]+=n;
				}
				else {
					ll cur=L;
					if(cur%j==0) {
						dp[0]+=n;
						cur++;
						dp[cur-L]-=n;
					}
					else if(cur%j+K>=j) {
						dp[0]+=n;
						cur=(cur/j+1)*j+1;
						dp[cur-L]-=n;
					}
					while(cur-L<=1500) {
						assert(cur%j<j-K);
						cur+=(j-K)-cur%j;
						dp[cur-L]+=n;
						cur=(cur/j+1)*j+1;
						if(cur-L>2000) break;
						dp[cur-L]-=n;
					}
				}
			}
			for(ll a=L;a<=R;a++) {
				if(a>L) dp[a-L]+=dp[a-L-1];
				if(dp[a-L]<N) continue;
				x=lower_bound(ALL(P),a+K+1)-lower_bound(ALL(P),a);
				mi=min(mi,N-x);
			}
			
			
		}
		cout<<mi<<endl;
		
	}
}

まとめ

本番なんか手間取ってるな。