kmjp's blog

競技プログラミング参加記です

AtCoder ARC #032 : D - アットコーダーモンスターズ

ARC

久々に本番Dが解けた。
http://arc032.contest.atcoder.jp/tasks/arc032_4

問題

N匹のモンスターがおり、それぞれの攻撃力はA[i]、防御力がD[i]とする。
このうちK匹を選択してチームを作りたい。

２匹のモンスターについて、攻撃力の差および防御力の差の大きい方がその２匹の不安定度となる。
チーム全体の不安定度は、チーム内の各２匹の不安定度の最大値となる。

チームを作成する際の最小の不安定度を求めよ。
また、同じ不安定度となるチーム構成数を求めよ。

解法

(A[i],D[i])を２次元座標上にプロットすると、問題は以下のように置き換えられる。
「プロットした点をK個以上辺上または内部に含められるような、(各辺が軸に平行な)最小の正方形の１辺の長さLを求めよ。また、そのような正方形に含められるようなK点の選び方の組み合わせを求めよ。」

まず長さLを求める。
これは長さLを二分探索して求めればよい。
先に２次元の累積和を取っておくと正方形内の点の数はO(1)で求められるので、各格子点(x,y)を総当たりし、そこを左下の頂点とする正方形内の点数を総当たりする。

次に組み合わせを求める。
また各格子点(x,y)を左下頂点とする正方形を総当たりし、K点以上正方形内に含められる格子点を探す。
この際、同じケースを複数カウントしないよう、X座標がxである点を１個以上含み、かつY座標がyである点を１個以上含むようにする。
これは包除定理で以下のように求める。
p(a,b)を点a,bから構成する正方形内または辺上に存在する点の数とする。
Combination(p( (x,y),(x+L,y+L) ),K) (正方形内の点からK個選択)
－ Combination(p( (x,y),(x+L,y+L) ) - p( (x,y),(x,y+L) ),K) (X座標がxにある点を１個も選ばないケースを引く)
－ Combination(p( (x,y),(x+L,y+L) ) - p( (x+L,y),(x,y) ),K) (Y座標がyにある点を１個も選ばないケースを引く)
＋ Combination(p( (x,y),(x+L,y+L) ) - p( (x+L,y),(x,y) ) - p( (x+L,y),(x,y) ) + p( (x,y),(x,y) ),K) (X座標がxにある点を１個も選ばないケースかつY座標がyにある点を１個も選ばないケースを引きすぎたので戻す)

int N,K;
ll mo=1000000007;
int A[101000],B[101000];
int mat[4200][4200];
int S[4200][4200];

ll combi(ll N_, ll C_) {
	const int NUM_=120001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

bool isok(int w) {
	ll num=0;
	int y,x;
	
	for(y=0;y+w<4100;y++) {
		for(x=0;x+w<4100;x++) {
			if(S[y+w][x+w]-S[y][x+w]-S[y+w][x]+S[y][x]>=K) return true;
		}
	}
	return false;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) {
		cin>>x>>y;
		x++,y++;
		A[i]=y,B[i]=x;
		mat[y][x]++;
	}
	for(y=1;y<=4100;y++) {
		for(x=1;x<=4100;x++) S[y][x]=S[y][x-1]+mat[y][x];
		for(x=1;x<=4100;x++) S[y][x]+=S[y-1][x];
	}
	
	int w=0;
	for(i=11;i>=0;i--) if(isok(w+(1<<i))==false) w+=1<<i;
	_P("%d\n",w);
	w++;
	
	
	ll ret=0;
	for(y=1;y<3003;y++) {
		for(x=1;x<3003;x++) {
			i=S[min(3002,y+w-1)][min(3002,x+w-1)]-S[y-1][min(3002,x+w-1)]-S[min(3002,y+w-1)][x-1]+S[y-1][x-1];
			if(i<K) continue;
			
			int my=mat[y][x];
			int mw=S[y][min(3002,x+w-1)]-S[y-1][min(3002,x+w-1)]-S[y][x]+S[y-1][x];
			int mh=S[min(3002,y+w-1)][x]-S[min(3002,y+w-1)][x-1]-S[y][x]+S[y][x-1];
			if(my+mw==0 || my+mh==0) continue;
			
			ret+=combi(i,K);
			ret+=mo-combi(i-my-mh,K);
			ret+=mo-combi(i-my-mw,K);
			ret+=combi(i-my-mh-mw,K);
			
			ret %= mo;
		}
	}
	_P("%lld\n",ret);
}

まとめ

二分探索まではすぐ思いついて、そのあと数え上げに悩んだ。
最終的に解ききれてよかった。