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; }