Codeforces Beta Round #95 (Div. 2) E : Yet Another Task with Queens

問題概要

N*N(N<10^5)のチェス盤にM(<10^5)のクイーンが配置されている。各クイーンに対して、範囲に含められているクイーンの数を数え、その分布を出力する問題。

解法

縦、横、斜め*2について独立に考える。例えば縦での衝突を考えるとき、列の違うクイーンはまったく関与しない。同じ列のクイーンを集めてソートしてやると、端のクイーンだけは1つのクイーンの範囲に含まれ、それ以外は2つのクイーンに含まれることが分かる。これを真面目にカウントするだけ。計算量もM*log M程度で抑えられていることが少し考えれば分かる。

practiceで通ったコード

計算量O(N + M*log M)くらい。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int MAX_N = 100000;

int ts[9];

int N, M;
int ds[MAX_N];
pair<int,int> ps[MAX_N]; //(x, y)

void count(vector< vector<pair<int,int> > >& vs){
	const int L = vs.size();
	for(int i=0; i<L; i++){
		if(vs[i].size() >= 2){
			ds[vs[i][0].second]++;
			ds[vs[i].back().second]++;
			for(int k=1, M=(int)vs[i].size() - 1; k<M; k++){
				ds[vs[i][k].second] += 2;
			}
		}
	}
}

void solve(){

	//横方向
	{
		vector< vector< pair<int,int> > > vs(N); //(x座標, id)
		for(int i=0; i<M; i++){
			vs[ps[i].second].push_back(make_pair(ps[i].first, i));
		}
		for(int i=0; i<N; i++){
			sort(vs[i].begin(), vs[i].end());
		}
		count(vs);
	}

	//縦方向
	{
		vector< vector< pair<int,int> > > vs(N); //(y座標, id)
		for(int i=0; i<M; i++){
			vs[ps[i].first].push_back(make_pair(ps[i].second, i));
		}
		for(int i=0; i<N; i++){
			sort(vs[i].begin(), vs[i].end());
		}
		count(vs);
	}

	//斜め１
	{
		vector< vector< pair<int,int> > > vs(2*N-1); //(y座標, id)
		for(int i=0; i<M; i++){
			int x = ps[i].first, y = ps[i].second;
			vs[x+y].push_back(make_pair(y, i));
		}
		for(int i=0; i<2*N-1; i++){
			sort(vs[i].begin(), vs[i].end());
		}
		count(vs);
	}

	//斜め２
	{
		vector< vector< pair<int,int> > > vs(2*N-1); //(y座標, id)
		for(int i=0; i<M; i++){
			int x = ps[i].first, y = ps[i].second;
			vs[x+(N-y-1)].push_back(make_pair(y, i));
		}
		for(int i=0; i<2*N-1; i++){
			sort(vs[i].begin(), vs[i].end());
		}
		count(vs);
	}

	for(int i=0; i<M; i++){
		ts[ds[i]]++;
	}

	//output
	for(int i=0; i<9; i++){
		printf("%d%c", ts[i], i==8?'\n':' ');
	}
}

int main(){

	scanf("%d%d", &N, &M);
	for(int i=0; i<M; i++){
		int x, y;
		scanf("%d%d", &x, &y);
		x--; y--;
		ps[i] = make_pair(x, y);
	}
	solve();
	return 0;
}