PKU演習問メモ(6/16)

No. 問題名 問題の種類および解法 難易度
3104 Drying 二分法 ★★★☆☆
3254 Corn Fields ビットDP ★★☆☆☆
2951 Cake Cutting メモ化探索 ★★☆☆☆

3104 Drying

問題概要

n枚の洗濯物がある。それぞれの水分の量はa[i]であり、毎分1ずつ水分が蒸発する。
また、乾燥機を使うことができ、乾燥機を使うと洗濯物のうち1枚だけ、その1分間だけ水分の蒸発する量をkにすることができる。


今、n,それぞれのa,kが与えられたとき、全ての洗濯物を乾かすのに必要な時間の最小値を求めよ。

n≦100000,
a[i],k≦10^9である。

解法

nの大きさからO(nlogn)くらいの解法が予想される。


ある時間mで洗濯物が乾かせるかどうかは、O(n)でわかる。
すなわち、それぞれの洗濯物について自然乾燥で減る水分の量がmなので、乾燥機で乾かす水分の量はa[i]-m
乾燥機を使うことで1回につきk-1の水分を余分に乾かせるので、乾燥機を使う回数はa[i]-m/(k-1)回(切り上げ)である。
これを全ての洗濯物のついて足し合わせ、m回以下になっているかどうか判定すればよい。


あとはこのようなmを二分法で動かすことで答えを求めることができる。
が、時間制限が厳しいのでm分で洗濯物が乾かせないとわかったらすぐに枝刈りをしないとTLEになってしまう。
なお、以下のコードではあらかじめkから1を減じてある。

ソースコード
int n,k,a[100000];

bool ok(ll m)
{
	ll sum=0;
	rep(i,n)
	{
		ll d=max(a[i]-m,0ll);
		sum+=d/k+(d%k!=0);
		if(sum>m)return 0;
	}
	return sum<=m;
}

int main()
{
	ll lo=0,hi=0,mid;
	
	scanf("%d",&n);
	rep(i,n)scanf("%d",a+i),hi+=a[i];
	scanf("%d",&k); k--;
	
	if(k==0)
	{
		cout<<*max_element(a,a+n)<<endl; return 0;
	}
	
	hi=hi/k+(hi%k!=0);
	
	while(hi>lo+1)
	{
		mid=(hi+lo)/2;
		if(ok(mid))hi=mid;
		else lo=mid;
	}
	cout<<hi<<endl;
	
	return 0;
}

3254 Corn Fields

問題概要

縦m,横nマスのグリッドで表される畑があり、各グリッドに牧草を植えたい。
いま、

  • 各グリッドが牧草に適しているかどうかそれぞれ0,1で与えられる
  • 牧草を植えたグリッド同士が隣接していてはならない(斜めはOK)

とき、全ての牧草の植え方の場合の数をmod 100000000で求めよ。
n,m≦12である。

解法

一列分の牧草の植え方は最大4000通りしかなく、「ある列の次の列の牧草の植え方」は、直前の列にしか依存しないので、最前列の植え方をビットで表した整数をインデックスにしてDPすればよい。
具体的には、dp[i][j]にi列目まででi列目の牧草の植え方がjであるときの場合の数を持っておく。

ソースコード
int mod=100000000;
int dp[13][1<<12];
bool f[12][12];

int main()
{
	int h,w; cin>>h>>w;
	rep(i,h)rep(j,w)cin>>f[i][j];
	
	rep(i,h+1)fill_n(dp[i],1<<w,0);
	dp[0][0]=1;
	
	for(int i=1;i<=h;i++)
	{
		rep(j,1<<w)rep(k,1<<w)if((j&k)==0)
		{
			rep(l,w)if((!f[i-1][l]&&(k&1<<l)))goto NEXT;
			rep(l,w-1)if((k&1<<l)&&(k&1<<l+1))goto NEXT;
			
			dp[i][k]+=dp[i-1][j]; dp[i][k]%=mod;
			
			NEXT:;
		}
	}
	
	int ans=0;
	rep(i,1<<w)ans+=dp[h][i],ans%=mod;
	cout<<ans<<endl;
	
	return 0;
}

2951 Cake Cutting

問題概要

幅w,高さhの長方形のケーキがある。これを「今まで得られた長方形をさらにその辺に平行に切り分ける」という操作を何回か繰り返すことで、m個の長方形に切り分けたい。
なお、全ての長方形の辺の長さは整数でなければならない。


w,h,m≦20を満たす。

解法

辺の長さが整数であり、十分小さいのでケーキの切り方を全て調べればよい。
ただしメモ化は必要(だと思われる)

ソースコード
int memo[21][21][21];

int rec(int w,int h,int m)
{
	if(w*h<m)return inf;
	if(w>h)swap(w,h);
	if(memo[w][h][m]>=0)return memo[w][h][m];
	if(m==0)return memo[w][h][m]=w*h;
	
	//縦にカット
	int ret=inf;
	for(int H=1;H<h;H++)for(int M=0;M<m;M++)
	ret=min(ret,max(rec(w,H,M),rec(w,h-H,m-1-M)));
	//横
	for(int W=1;W<w;W++)for(int M=0;M<m;M++)
	ret=min(ret,max(rec(W,h,M),rec(w-W,h,m-1-M)));
	
	return memo[w][h][m]=ret;
}

int main()
{
	rep(i,21)rep(j,21)rep(k,21)memo[i][j][k]=-1;
	
	int w,h,m;
	while(cin>>w>>h>>m,w)
	{
		cout<<rec(w,h,m-1)<<endl;
	}
	
	return 0;
}