Codeforces ECR #093 : G. Running Competition

想定解ではなかった。
https://codeforces.com/contest/1398/problem/G

問題

以下のような配線を考える。
(0,0)-(X,0)-(X,Y)-(0,Y)-(0,0)と矩形状に配線がなされている。
その他、N個のX座標A[i]において、(A[i],0)-(A[i],Y)の間に配線がなされている。

ここでクエリとして正整数Lが与えられる。
配線のうちいくつかを使用して構成できる矩形のうち、長さがLの倍数のものがあるか。
あるならその最大値を求めよ。

解法

事前にあり得る長さを列挙しておこう。
Lの倍数で有効なものをチェックするのはO*1で列挙できる。

あり得る長さの列挙は、bitsetでO(NX)でも間に合ってしまう。
あいにく、想定はFFTによる列挙だった様子。

int N,X,Y;
int A[202020];
int Q;
int L[202020];
int ret[505050];

bitset<202020> BS,CS;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X>>Y;
	FOR(i,N+1) {
		cin>>A[i];
		BS[A[i]]=1;
	}
	FOR(i,N) CS |= BS>>A[i];
	
	
	MINUS(ret);
	for(i=1;i<=500000;i++) {
		if(i>Y&&i-Y<=X&&CS[i-Y]) {
			for(j=i;j<=500000;j+=i) ret[j]=i*2;
		}
	}
	
	
	cin>>Q;
	FOR(i,Q) {
		cin>>x;
		cout<<ret[x/2]<<" ";
		
	}
	cout<<endl;
}

まとめ

もう少しNかXが大きければO(NX)通らなかったのにね。

*1:X+Y)/L)でできるので、異なるLに対しては均しでO((X+Y)log(X+Y