PKU演習問メモ(8/2)

暑いし体だるいし頭動かないし眠れない。

No. 問題名 問題の種類および解法 難易度
1984 Navigation Nightmare Union-find ★★★☆☆
2948 Martian Mining 動的計画法 ★★☆☆☆

1984 Navigation Nightmare

問題概要

座標平面上にn個の牧場がある。
それらの位置の関係がm個、
"F1の(東西南北の方向)距離dのところにF2"あるという形式で与えられる。


このとき、次のようなクエリに答えよ。

  • I個目までの位置関係の情報で、F1とF2のマンハッタン距離を求められるのならその距離を、不可能なら-1を返す


ただし、n,m≦40000かつ
クエリの数kはk≦10000を満たす。

解法

マンハッタン距離は、一度決まってしまえば後は変わらない。
したがって、最初に全ての牧場の座標を計算しておき、クエリを求めるときに、それらがI番目までで求まるかどうかだけを調べればよい。


それには、まず入力を全て読み込み、クエリをIの順にソートして、
union-findを使い関係が求まるかを決めながら答えを配列に書き、
配列を求められている答えの順にソートして出力すればよい。


実装量はやや多目。

ソースコード
int n,m,q;
int f1[40000],f2[40000];
struct Q{
	int f1,f2,I,id;
	bool operator<(const Q &r)const{
		return I<r.I;
	}
};
Q qin[10000];
pi ans[10000];

int north[40000],east[40000],west[40000],south[40000];
int nd[40000],ed[40000],wd[40000],sd[40000];
int X[40000],Y[40000],p[40000];

//union-find
int root(int x)
{
	if(p[x]==x)return x;
	return p[x]=root(p[x]);
}
void merge(int a,int b)
{
	a=root(a); b=root(b);
	if(a!=b)p[b]=a;
}

void load(int &s,int t)
{
	for(;s<t;s++)merge(f1[s],f2[s]);
}
int dist(int f1,int f2)
{
	if(root(f1)!=root(f2))return -1;
	if(X[f1]==inf||X[f2]==inf||Y[f1]==inf||Y[f2]==inf)return -1;
	
	return abs(X[f1]-X[f2])+abs(Y[f1]-Y[f2]);
}

//coodinate calculating
void dfs(int c)
{
	int t;
	if(nd[c]!=-1&&X[t=north[c]]==inf)X[t]=X[c],Y[t]=Y[c]+nd[c],dfs(t);
	if(sd[c]!=-1&&X[t=south[c]]==inf)X[t]=X[c],Y[t]=Y[c]-sd[c],dfs(t);
	if(ed[c]!=-1&&X[t=east[c]]==inf)X[t]=X[c]+ed[c],Y[t]=Y[c],dfs(t);
	if(wd[c]!=-1&&X[t=west[c]]==inf)X[t]=X[c]-wd[c],Y[t]=Y[c],dfs(t);
}

int main()
{
	scanf("%d%d",&n,&m);
	rep(i,n)nd[i]=ed[i]=wd[i]=sd[i]=-1;
	rep(i,m){
		int a,b,d; char c;
		scanf("%d%d%d %c",&a,&b,&d,&c);
		f1[i]=--a; f2[i]=--b;
		if(c=='N')north[a]=b,south[b]=a,nd[a]=sd[b]=d;
		else if(c=='S')north[b]=a,south[a]=b,sd[a]=nd[b]=d;
		else if(c=='E')east[a]=b,west[b]=a,ed[a]=wd[b]=d;
		else east[b]=a,west[a]=b,wd[a]=ed[b]=d;
	}
	rep(i,n)X[i]=Y[i]=inf,p[i]=i;
	rep(i,n)if(X[i]==inf)X[i]=Y[i]=0,dfs(i);
	
	scanf("%d",&q);
	rep(i,q){
		int a,b;
		scanf("%d%d%d",&a,&b,&qin[i].I),qin[i].id=i;
		qin[i].f1=a-1; qin[i].f2=b-1;
	}
	sort(qin,qin+q);
	
	int cur=0;
	rep(i,q)
	{
		if(cur<qin[i].I)load(cur,qin[i].I);
		ans[i]=mp(qin[i].id,dist(qin[i].f1,qin[i].f2));
	}
	sort(ans,ans+q);
	rep(i,q)printf("%d\n",ans[i].second);
	
	return 0;
}

2948 Martian Mining

問題概要

nxmマスのグリッド上に2種類の金属yeyeniumとblogiumが分布しており、それをベルトコンベアを使って回収したい。
ベルトコンベアの向きは上向きまたは左向きのみであり、ベルトコンベアは同方向同士のものを連結することができる。
blogiumの回収基地はグリッド上部、yeyeniumの回収基地はグリッド左部である。


2種類の金属の分布が与えられたとき、回収できる金属の量の和の最大値を求めよ。
n,m≦500を満たす。

解法

動的計画法(メモ化再帰)による。
範囲(0,0)から(w,h)までの最適解は、

  • その長方形の右側に上へのベルトコンベアを作る
  • その長方形の下側に左へのベルトコンベアを作る

のいずれかになる。
それぞれの場合について、y,xを1減らして再帰が可能なため、それをコードにすればよい。

ソースコード
int h,w;
int blog[500][500],yeye[500][500];
int dp[501][501];

int rec(int y,int x)
{
	if(y<=0||x<=0)return 0;
	if(dp[y][x]!=-1)return dp[y][x];
	
	int bottom=0,right=0,ret=0;
	rep(i,x)bottom+=yeye[y-1][i];
	rep(i,y)right+=blog[i][x-1];
	ret=max(rec(y-1,x)+bottom,rec(y,x-1)+right);
	
	return dp[y][x]=ret;
}
int main()
{
	while(scanf("%d%d",&h,&w),h){
		rep(i,h)rep(j,w)scanf("%d",yeye[i]+j);
		rep(i,h)rep(j,w)scanf("%d",blog[i]+j);
		
		rep(i,h+1)fill_n(dp[i],w+1,-1);
		printf("%d\n",rec(h,w));
	}
	return 0;
}