PKU演習問メモ(7/15)
テスト週間……
| No. | 問題名 | 問題の種類および解法 | 難易度 |
|---|---|---|---|
| 2392 | Space Elevator | 動的計画法 | ★★★☆☆ |
| 2184 | Cow Exhibition | 動的計画法 | ★★★☆☆ |
| 1828 | Monkeys' Pride | 動的計画法 | ★★☆☆☆ |
| 1170 | Shopping Offers | 深さ優先探索 | ★★☆☆☆ |
| 1322 | Chocolate | 動的計画法・行列のべき乗 | ★★★☆☆ |
2392 Space Elevator
問題概要
k種類のブロックがある。それぞれの高さh[i],限界位置a[i],個数c[i]が与えられる。
できるだけ高いブロックを積み上げたいが、それぞれのブロックには限界位置があり、その高さをブロックのどこか一部が超えてはいけない。
このとき、ブロックを積み上げられる最大の高さを求めよ。
k≦400,
h[i]≦100,
c[i]≦10,
a[i]≦40000を満たす。
解法
まず、ブロックを限界位置の昇順にソートする。
ソート後、j種類目までのブロックで作れる高さが、i種類目までのブロックでも作れたとすると（i＜j）i番目までのブロックでその高さを作ってから、残りを同じように組み立てれば、j種類目までのブロックで作れる高さは全て作れる。
ソースコード
struct S{ int h,a,c; bool operator<(const S &r)const{ return a<r.a; } }; int k; S in[400]; bool dp[2][40001]; int main() { cin>>k; rep(i,k)cin>>in[i].h>>in[i].a>>in[i].c; sort(in,in+k); int cur=0,next=1; fill_n(dp[cur],40001,0); dp[0][0]=1; rep(i,k) { fill_n(dp[next],40001,0); rep(j,40001)if(dp[cur][j]) for(int l=0;l<=in[i].c&&j+in[i].h*l<=in[i].a;l++) dp[next][j+in[i].h*l]=1; swap(cur,next); } int ans=40000; for(;;ans--)if(dp[cur][ans])break; cout<<ans<<endl; return 0; }
2184 Cow Exhibition
問題概要
牛の品評会をする。n匹の牛のそれぞれの賢さと面白さがs[i],f[i]で与えられる。
この中から0匹以上の品評会に出す牛を選び、評価の合計値（品評会に出す牛のs[i],f[i]の全ての和）を最大にしたい。
ただし、s[i]の合計値とf[i]の合計値はいずれも負になってはならない。
このとき、評価の合計値の最大値を求めよ。
- 1000≦s[i],f[i]≦1000を満たす。
解法
計算途中では、s[i],f[i]の和の負の値も許可することにする。
すると普通の動的計画法の問題になる。
（s[i]の和ごとにf[i]の最大値を持っておきながら、更新していく）
最後に和の最大値を求める段階で0以上の値を用いればよい。
ソースコード
const int MX=200001,HALF=100000; int n; int s[100],f[100]; int dp[2][MX]; int main() { scanf("%d",&n); rep(i,n)scanf("%d%d",s+i,f+i); fill_n(dp[0],MX,-inf); int cur=0,next=1; rep(i,n) { rep(j,MX)dp[next][j]=dp[cur][j]; dp[next][s[i]+HALF]=max(dp[cur][s[i]+HALF],f[i]); rep(j,MX)if(0<=j+s[i]&&j+s[i]<MX&&dp[cur][j]!=-inf) { dp[next][j+s[i]]=max(dp[next][j+s[i]],dp[cur][j]+f[i]); } swap(cur,next); } int ans=0; for(int j=HALF;j<MX;j++)if(dp[cur][j]>0)ans=max(ans,j-HALF+dp[cur][j]); cout<<ans<<endl; return 0; }
1828 Monkey's Pride
問題概要
座標平面上のn匹の猿の座標が与えられる。
(x,y)にいる猿は、x≦Xかつy≦Yであるような座標(X,Y)の猿がいないときボスになれる。
n匹の中にボスになれる猿が何匹いるかを求めよ。
解法
猿の座標をx座標の順にソートする。
一番右の猿から、今まで見た猿の中での最大y座標を覚えておけば、O(1)で自分の右上に猿がいるかどうか判定できる。
（今まで見た猿はX座標が全て最新の猿より大きいため、y座標の値だけを見ればよくなる）
ソースコード
int n,mxi[50000]; pi p[50000]; int main() { while(scanf("%d",&n),n) { int x,y; rep(i,n)scanf("%d%d",&x,&y),p[i]=mp(x,y); int ans=1; sort(p,p+n); mxi[n-1]=n-1; for(int i=n-2;i>=0;i--) { if(p[mxi[i+1]].second<p[i].second)ans++,mxi[i]=i; else mxi[i]=mxi[i+1]; } printf("%d\n",ans); } return 0; }
1170 Shopping Offers
問題概要
b種類の商品を買いたい。
i番目(0≦i＜b)の商品のID番号はc[i]であり、買う個数はk[i]、正規の値段はp[i]である。
今s種類の割引があり、割引の仕方が以下のような数字の並びで与えられる。
(商品の種類の数) (ID) (個数) (ID) (個数)…… 割引後の値段
最適の割引を組み合わせたとき、支払い金額の合計を求めよ。
ただし、買いたい商品以外を余分に購入することは許されない。
0≦b≦5,0≦s≦99,
c[i],p[i]≦999,
k[i]≦5を満たす。
解法
状態数は最大で6^5（=4万強）と小さいので深さ優先探索をすれば間に合う。
statusを見るにボトムアップのDPをすれば10倍くらい速い気がするけど……
探索は以下のように書いた。
- 残りの商品を全て正規の値段で買った場合の価格が最安だったらテーブルを更新
- s種類の割引について可能なものを全て適用して再帰
ソースコード
int b,s; int c[5],k[5],p[5],offerp[100]; vector<vector<pi> > offer; const int MX=6*6*6*6*6; int cost[MX]; void dfs(int cur) { int rest=0; bool ok=1; rep(i,b) { rest+=k[i]*p[i]; if(k[i])ok=0; } cost[0]=min(cost[0],cur+rest); if(ok)return; rep(i,s) { int hash; rep(j,offer[i].size())if(k[offer[i][j].first]<offer[i][j].second)goto FAIL; rep(j,offer[i].size())k[offer[i][j].first]-=offer[i][j].second; hash=0; rep(j,b)hash*=6,hash+=k[j]; if(cost[hash]>cur+offerp[i]) { cost[hash]=cur+offerp[i]; dfs(cur+offerp[i]); } rep(j,offer[i].size())k[offer[i][j].first]+=offer[i][j].second; FAIL:; } } int main() { offer.clear(); cin>>b; rep(i,b)cin>>c[i]>>k[i]>>p[i]; cin>>s; offer.resize(s); rep(i,s) { int t,x,y; cin>>t; rep(j,t) { cin>>x>>y; x=find(c,c+b,x)-c; offer[i].pb(mp(x,y)); } cin>>offerp[i]; } fill_n(cost,MX,inf); dfs(0); cout<<cost[0]<<endl; return 0; }
1322 Chocolate
問題概要
c色のチョコレートが入った箱を用い、以下の試行をn回繰り返す。
- 箱からチョコレートを一つ取り出し、テーブルに置く
- テーブルに同じ色のチョコレートが二つあったらそれを全て食べる
n回の試行の後にテーブルにm色のチョコレートがある確率を求めよ。
ただし、箱には十分沢山のチョコレートがあり、毎回の試行においてそれぞれのチョコレートが取り出される確率は等しく1/cであるものとする。
c≦100,
n,m≦1000000を満たす。
解法
i回目の試行の直前にテーブルにj色のチョコレートがある確率をdp[i][j]とすると、
漸化式は次のようにして立てられる。
- dp[i+1][j+1]=dp[i][j]+(j色以外のチョコレートを取り出す確率)
- dp[i+1][j-1]=dp[i][j]+(j色のどれかのチョコレートを取り出す確率)
したがって漸化式にしたがって動的計画法をすればよい。
……と思ったらTLE.
だったので確率の計算を行列のべき乗でやり、べき乗を繰り返し二乗法により高速化するようにすればよい。
……と思ったら定数項がnが小さい時に無駄に時間がかかる（行列の掛け算1回ごとにのc^3の掛け算が必要）ためTLE.
なのでnが小さいときは動的計画法、nが大きいときは行列のべき乗を用いるようにすると制限時間ギリギリで通る。
（想定解法は違ったみたい）
ソースコード
struct M{ int size; double a[101][101]; M(int s):size(s){} M operator*(const M &r){ M ret(size); rep(i,size)fill_n(ret.a[i],size,0); rep(i,size)rep(j,size)rep(k,size) { ret.a[i][j]+=a[i][k]*r.a[k][j]; } return ret; } }; int c,n,m; double dp[2][101]; double calcDP() { fill_n(dp[0],c+1,0); dp[0][0]=1; int cur=0,next=1; rep(i,n) { fill_n(dp[next],c+1,0); rep(j,c+1) { if(j)dp[next][j-1]+=dp[cur][j]*j/c; if(j<c)dp[next][j+1]+=dp[cur][j]*(c-j)/c; } swap(cur,next); } return dp[cur][m]; } double calcMat() { M ans(c+1),tmp(c+1); rep(i,c+1)rep(j,c+1)ans.a[i][j]=i==j; rep(i,c+1) { rep(j,c+1)tmp.a[i][j]=0; if(i<c)tmp.a[i][i+1]=(i+1)*1.0/c; if(i>0)tmp.a[i][i-1]=(c-i+1)*1.0/c; } for(int i=1;;tmp=tmp*tmp) { if(n&i)ans=ans*tmp; i<<=1; if(i>n)break;; } return ans.a[m][0]; } int main() { while(scanf("%d",&c),c) { scanf("%d%d",&n,&m); if(m>c) { printf("%.3f\n",0.0); continue; } printf("%.3f\n",n<50000?calcDP():calcMat()); } return 0; }
