Codeforces ECR #098 : E. Two Editorials

だいぶ難しめっぽかった回。
https://codeforces.com/contest/1452/problem/E

問題

1～Nのうちの区間[L[i],R[i]]がM個与えられる。
1～Nの区間から、長さKの区間を2つ取ったとする。
各M個の区間に対し、それぞれ後者の2つの区間のうち共通部分のうち長い方の長さをスコアとする。
得られる総スコアの最大値を求めよ。

解法

1個目の長さKの区間の位置[x,x+K)を操作しながら、2個目の位置[y,y+K)それぞれにおいて得られるスコアの合計を計算していく。
もしある区間[L[i],R[i]]と、[x,x+K)の共通部分の長さがsの時、[y,y+K)と[L[i],R[i]]との共通部分の長さがtなら、2個目によって得られるスコアはmax(0,t-s)である。
xを操作するとsが最大で±1変化するので、t=s±1であるような位置のスコアを更新していこう。

int N,M,K;
int L[2020],R[2020];
int C[2020][4020];
vector<int> pos[2020][2020];

template<class V, int ME> class BIT {
public:
	V bit[1<<ME];
	V operator()(int e) {if(e<0) return 0;V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;}
	void add(int e,V v) { e++; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;}
};
BIT<int,15> bt;


int num(int a,int b,int x,int y) {
	a=max(a,x);
	b=min(b,y);
	return max(0,b-a);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	FOR(i,M) {
		cin>>L[i]>>R[i];
		L[i]--;
		for(x=0;x+K<=2*N;x++) {
			C[i][x]=num(x,x+K,L[i],R[i]);
			//cout<<C[i][x];
			pos[i][C[i][x]].push_back(x);
			if(x==0) bt.add(x,C[i][x]);
			else bt.add(x,max(C[i][x],C[i][0])-max(C[i][x-1],C[i][0]));
		}
		
	}
	
	int ret=0;
	for(x=0;x+K<=N;x++) {
		if(x) {
			FOR(i,M) {
				if(C[i][x]>C[i][x-1]) {
					y=pos[i][C[i][x]].back()+1;
					bt.add(y,1);
				}
				if(C[i][x]<C[i][x-1]) {
					bt.add(x,-1);
				}
			}
			
		}
		int ma=0;
		//for(y=x;y+K<=N;y++) cout<<y<<":"<<bt(y)<<" ";
		for(y=x;y+K<=N;y++) ma=max(ma,bt(y));
		//cout<<x<<" "<<ma<<endl;
		ret=max(ret,ma);
	}
	cout<<ret<<endl;
	
}

まとめ

7問回の5問目にしては難しめ。