Codeforces ECR #135 : G. Illumination

たまにCFって妙に実行時間の長い問題が出るな。
https://codeforces.com/contest/1728/problem/G

問題

[0,d]の座標からなる1次元の領域がある。
ここにN箇所のランタンがあり、M個の着目点がある。
各ランタンには、強さを0～dの整数値で設定でき、ランタンの座標を中心にその強さを半径とする区間を照らすことができる。

以下のクエリに答えよ。
ランタンが1個追加される。
各ランタンの強さの組み合わせのうち、全着目点が最低1個以上のランタンで照らされた状態になるのは何通りか。

解法

以下を事前に計算しておく。
dp(x,y) := 着目点のうち、照らされない最も左のものがx番目、右のものがy番目であるような、N個のランタンの強さの設定
x番目より左と、y番目より右の着目点がすべて照らされているケースを、包除原理の要領で省いていこう。

各クエリに対しては、各dp(x,y)に対し、追加したランタンがx,yの着目点を両方カバーしないような強さの範囲を求めればよい。

int D,N,M,Q;
int L[202020],P[202020];

ll dp[20][20];
ll dpL[20];
ll dpR[20];

const ll mo=998244353;
ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>D>>N>>M;
	vector<pair<int,int>> V;
	FOR(i,N) {
		cin>>L[i];
	}
	FOR(i,M) {
		cin>>P[i];
		FOR(j,N) if(P[i]==L[j]) break;
		if(j<N) i--,M--;
	}
	sort(L,L+N);
	sort(P,P+M);
	
	FOR(y,M) FOR(x,y+1) {
		dp[x][y]=1;
		FOR(i,N) if(P[x]<L[i]&&L[i]<P[y]) (dp[x][y]*=min(P[y]-L[i],L[i]-P[x]))%=mo;
	}

	FOR(x,M) {
		dpL[x]=1;
		FOR(j,N) if(L[j]<P[x]) (dpL[x]*=P[x]-L[j])%=mo;
		FOR(y,x) (dpL[x]+=mo-dpL[y]*dp[y][x]%mo)%=mo;
	}
	for(x=M-1;x>=0;x--) {
		dpR[x]=1;
		FOR(j,N) if(L[j]>P[x]) (dpR[x]*=L[j]-P[x])%=mo;
		for(y=x+1;y<M;y++) (dpR[x]+=mo-dpR[y]*dp[x][y]%mo)%=mo;
	}
	
	FOR(y,M) FOR(x,y+1) {
		(dp[x][y]*=dpL[x]*dpR[y]%mo)%=mo;
	}
	
	cin>>Q;
	while(Q--) {
		int C;
		cin>>C;
		
		ll ret=modpow(D+1,N+1);
		FOR(y,M) FOR(x,y+1) {
			ret+=mo-dp[x][y]*max(abs(C-P[x]),abs(C-P[y]))%mo;
		}
		cout<<ret%mo<<endl;
	}
	
}

まとめ

包除原理の部分、EditorialではO(2^M)かけてるけど、O(M^2)でも行ける気がする。