tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

AOJ 0509,0585

残り少ないVolume 5。一応JOIのチューターなのでソースを書いてみたりするなど。
0509:
O(N^2)をかけば通る。それより速い解法もあるんじゃないかなあ。どうなんだろう

#include<stdio.h>
#include<algorithm>
using namespace std;
int dp[2][10000];
pair<pair<int,int>,pair<int,int> >event[20000];
int main(){
	int a,b;
	while(scanf("%d%d",&a,&b),a){
	int xm=0;
	int ym=0;
	for(int i=0;i<a;i++){
		int p,q,r,s;
		scanf("%d%d%d%d",&p,&q,&r,&s);
		event[i*2]=make_pair(make_pair(p,1),make_pair(q,s));
		event[i*2+1]=make_pair(make_pair(r,-1),make_pair(q,s));
		xm=max(xm,r);
		ym=max(ym,s);
	}
	std::sort(event,event+a*2);
	
	for(int i=0;i<2;i++)
		for(int j=0;j<ym;j++)
			dp[i][j]=0;
	int S=0;
	int D=0;
	int at=0;
	for(int i=0;i<=xm;i++){
		int u=i&1;
		for(int j=0;j<ym;j++)dp[u][j]=dp[!u][j];
		for(;at<2*a&&event[at].first.first==i;at++){
			for(int j=event[at].second.first;j<event[at].second.second;j++)dp[u][j]+=event[at].first.second;
		}
		for(int j=0;j<ym;j++)if(dp[u][j])S++;
		for(int j=0;j<ym;j++)if((dp[u][j]||dp[!u][j])&&!(dp[u][j]&&dp[!u][j]))D++;
		for(int j=0;j<ym-1;j++)if((dp[u][j]||dp[u][j+1])&&!(dp[u][j]&&dp[u][j+1]))D++;
		if(dp[u][0])D++;
		if(dp[u][ym-1])D++;
	}
	printf("%d\n",S);
	if(b==2)printf("%d\n",D);
}}

0585:
典型のあれ書くのが面倒だったのでバケット法で嘘解法しました。ケースによってはこのコードだと落ちるが、ゆるいデータセットなのでセーフ。

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int x[500000];
int y[500000];
vector<int>bag[201][201];
int dx[]={1,1,1,0,0,0,-1,-1,-1};
int dy[]={1,0,-1,1,0,-1,1,0,-1};
int main(){
	int a;
	scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%d%d",x+i,y+i);
		x[i]+=10000;
		y[i]+=10000;
		bag[x[i]/100][y[i]/100].push_back(i);
	}
	int ret=999999999;
	if(a<=100){
		for(int i=0;i<a;i++){
			for(int j=i+1;j<a;j++)ret=min(ret,(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
		}
		printf("%d\n",ret);
		return 0;
	}
	for(int i=0;i<a;i++){
		int R=x[i]/100;
		int W=y[i]/100;
		for(int j=0;j<9;j++){
			if(0<=R+dx[j]&&R+dx[j]<201&&0<=W+dy[j]&&W+dy[j]<201){
				for(int k=0;k<bag[R+dx[j]][W+dy[j]].size();k++){
					if(i!=bag[R+dx[j]][W+dy[j]][k])
					ret=min(ret,(x[i]-x[bag[R+dx[j]][W+dy[j]][k]])*(x[i]-x[bag[R+dx[j]][W+dy[j]][k]])+(y[i]-y[bag[R+dx[j]][W+dy[j]][k]])*(y[i]-y[bag[R+dx[j]][W+dy[j]][k]]));
				}
			}
		}
	}
	printf("%d\n",ret);
}

UNSOLVED VOLUME 5

0508: String With Rings
どう考えても枝刈りゲー。こういうの苦手だし嫌いだから埋めていない。

0548: Reindeer with no sense of direction
解けぬ(本番では時間を使いまくって解けた) 正しい探索をすると枝刈り楽らしいが、変な解法だとどうしようもない定数倍改善が必要になるらしい。

0581: Gifts
少し面倒なだけのDP。いつでも通せると思う。