PKU演習問メモ(4/28)

No.	Title	分類・解法	主観的難易度
2958	Pizza delivery	マンハッタン距離	★★★☆☆

以下問題概要（ｒｙ

2958 Pizza delivery

問題概要

hxwのグリッドで表される都市にピザの配送センターを作りたい。
配送の需要はわかっている（それぞれのグリッドごとにに何度配送すれば良いかは決まっている）
配送のコストが、配送回数xセンターからその場所へのマンハッタン距離で決まるとき、コストの総和を最小にするようなセンターの位置における、コストの総和を求めよ。

解法

各マスごとに配送のコストを愚直に求めるO(h^2w^2)の解法がすぐに思いうかぶが、それだとTLEになる（なった）ので何か工夫する必要がある。
マンハッタン距離が、縦の移動+横の移動で表され、縦の移動と横の移動は独立に足し算できることに注目すれば、行ごと、列ごとに配送件数を覚えておけばよいということに気づく。計算量はO(hw(h+w)).

ソースコード

int h,w,drow[100],dcol[100];

int main()
{
	int cs; cin>>cs;
	while(cs--)
	{
		cin>>w>>h;
		fill_n(drow,h,0); fill_n(dcol,w,0);
		
		rep(i,h)rep(j,w)
		{
			int d; cin>>d;
			drow[i]+=d,dcol[j]+=d;
		}
		
		int ans=inf;
		rep(i,h)rep(j,w)
		{
			int c=0;
			rep(k,h)c+=drow[k]*abs(k-i);
			rep(k,h)c+=dcol[k]*abs(k-j);
			
			ans=min(ans,c);
		}
		
		cout<<ans<<" blocks"<<endl;
	}
	return 0;
}

fill_nアルゴリズムの存在を今更知ったので使ってみた。