Zepto Code Rush 2015 : F. Pudding Monsters

これは自力ではわからない…。
http://codeforces.com/contest/526/problem/F

問題

N*NのグリッドにN個のセルにモンスターがいる。
各モンスター同士は、同じ列または同じ行にいることがない。

このグリッド上でK*Kの領域(Kは任意の整数)を選択するとき、中にK個のモンスターがいるような選び方は何通りあるか。

解法

Editorialを見て回答。

各列に対し、モンスターのいる行をP[i]とするとP[i]は1～NのPermutationとなる。
この問題は、P[x]～P[y]がある連続した(y-x+1)個の整数のPermutationとなるような(x,y)の対を求める問題と見なすことができる。

以下、P[L]～P[R]の間に条件を満たす(x,y)の対が何個あるか(DP(L,R))を求めていく。
MをL,Rの中点とする。
L≦x≦y＜Mであるような(x,y)はDP(L,M)、M≦x≦y＜Rであるような(x,y)はDP(M,R)に含まれていることがわかるので、DP(L,R)=DP(L,M)+DP(M,R)+(L≦x＜M≦y＜Rで条件を満たす(x,y)の数)となる。

DP(L,M),DP(M,R)は再帰的に計算できるので残りは最後の「L≦x＜M≦y＜Rで条件を満たす(x,y)の数」である。
xをL≦x＜Mの範囲で総当たりし、対応するyがいくつあるかを尺取法の要領で求めていく。

min(P[x]..P[M-1])＜min(P[M]..[y])かつmax(P[x]..P[M-1])＞max(P[M]..P[y])である場合、条件を満たすyはx+max(P[x]..P[M-1])-min(P[x]..P[M-1])である。
この時、x～yまでは(y-x+1)個の列があり、それらの間にあるP[i]の値はmax(P[x]..P[M-1])-min(P[x]..P[M-1])+1個で一致する。

そうでない場合、以下の2ケースで条件を満たす。

• min(P[x]..P[M-1])＜min(P[M]..[y])かつmax(P[x]..P[M-1])＜max(P[M]..P[y])かつmax(P[M]..P[y])-min(P[x]..P[M-1])==y-x
• min(P[x]..P[M-1])＞min(P[M]..[y])かつmax(P[x]..P[M-1])＞max(P[M]..P[y])かつmax(P[x]..P[M-1])-min(P[M]..P[y])==y-x

上記yを総当たりすると間に合わないので、尺取法を用いるとx毎に変化するyの量が小さくなり、全体の処理量が減る。

int N;
int X[400000];
int MX[400000],MN[400000];
ll ret;
int cnt1[800000],cnt2[800000];

ll dp(int L,int R) {
	if(L>=R) return 0;
	if(L+1==R) return 1;
	if(L+2==R) return 2+(abs(X[L]-X[L+1])==1);
	int M=(L+R)/2,i,x1,x2,y1,y2;
	ll ret = dp(L,M) + dp(M,R);
	
	MX[M]=MN[M]=X[M];
	MX[M-1]=MN[M-1]=X[M-1];
	for(i=M-2;i>=L;i--) MX[i]=max(MX[i+1],X[i]),MN[i]=min(MN[i+1],X[i]);
	for(i=M+1;i<R;i++)  MX[i]=max(MX[i-1],X[i]),MN[i]=min(MN[i-1],X[i]);
	
	for(i=L;i<R;i++) {
		int num=MX[i]-MN[i];
		if(i<M && i+num>=M && i+num<R && MX[i+num]<MX[i] && MN[i+num]>MN[i]) ret++;
		if(i>=M && i-num<M && i-num>=L && MX[i-num]<MX[i] && MN[i-num]>MN[i]) ret++;
	}
	
	for(i=M-1, x1=x2=y1=y2=M;i>=L;i--) {
		while(x1<R && MN[x1]>MN[i])  cnt1[MX[x1]-x1+400000]++, x1++;
		while(x2<x1 && MX[x2]<MX[i]) cnt1[MX[x2]-x2+400000]--, x2++;
		while(y1<R && MX[y1]<MX[i])  cnt2[y1+MN[y1]]++, y1++;
		while(y2<y1 && MN[y2]>MN[i]) cnt2[y2+MN[y2]]--, y2++;
		ret += cnt1[MN[i]-i+400000] + cnt2[i+MX[i]];
	}
	while(x2<x1) cnt1[MX[x2]-x2+400000]--, x2++;
	while(y2<y1) cnt2[y2+MN[y2]]--, y2++;
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>x>>y, X[x]=y;
	cout<<dp(1,N+1)<<endl;
}

まとめ

この再帰は思いつかない…。