第7回日本情報オリンピック 春合宿 1日目 問題3 「インフルエンザ」 (Flu)

以前バケット法でも解けますとか言ってたので解いた。

第7回日本情報オリンピック 春合宿 1日目 「インフルエンザ」 (Flu) - intさわだんのBlack History

バケット法については蟻本参照してください。

こういう問題すきです。

計算量はO(N)だと思うけれど定数係数がかなりアレなのでO(N)であってO(N)でないという哲学的なものになる。

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> P;
int n,m,d,k,ans;
P p[100003];
bool used[1002][1002];

int nj(int x){
	return (x*x);
}
vector<P> bucket[1003][1003];

int main(){
	map<P,int> ma;
	scanf("%d%d%d%d",&n,&m,&d,&k);
	for(int i = 1;i <= n;i++){
		scanf("%d%d",&p[i].first,&p[i].second);
		ma[P(p[i].first,p[i].second)] = i;
		bucket[p[i].first/d][p[i].second/d].push_back(P(p[i].first,p[i].second));
	}
	for(int i = 0;i <= 1000;i++){
		for(int j = 0;j <= 1000;j++){
			used[i][j] = false;
		}
	}
	queue<P> que;
	que.push(P(0,1));used[p[1].first][p[1].second] = true;
	while(que.size()){
		P q = que.front(); que.pop();
		if(q.first > k)continue;
		if(q.first <= k && q.first + m > k)ans++;
		int a1 = p[q.second].first/d;
		int a2 = p[q.second].second/d;
		int jo = bucket[a1][a2].size();
		for(int i = max(0,a1-1);i <= a1 + 1;i++){
			for(int j = max(0,a2-1);j <= a2 + 1;j++){
				int bs = bucket[i][j].size();
				for(int l = 0;l < bs;l++){
					P t = bucket[i][j][l];
					if(used[t.first][t.second] == false && nj(t.first-p[q.second].first)+nj(t.second-p[q.second].second) <= d*d){
						used[t.first][t.second] = true;
						que.push(P(q.first+1,ma[P(t.first,t.second)]));
					}
				}
			}
		}
	}
	printf("%d\n",ans);

	return 0;
}