PKU演習問メモ(8/19)
頭わるくてしにたい……
| No. | 問題名 | 問題の種類および解法 | 難易度 |
|---|---|---|---|
| 1972 | Dice Stacking | 実装 | ★★☆☆☆ |
| 1959 | Darts | 動的計画法 | ★★☆☆☆ |
| 1929 | Calories from Fat | 実装 | ★☆☆☆☆ |
| 1906 | Expanding Rods | 二分法 | ★★★☆☆ |
| 1961 | Period | 接頭文字列の繰り返し・KMP | ★★★★☆ |
1972 Dice Stacking
問題概要
n個のサイコロの展開図が与えられる。
それぞれのサイコロは各面が1から6の異なる整数であり、向かい合う面の和は必ずしも7にはなっていない。
このn個のサイコロを積み上げ、1x1xnの直方体を作る。
積み上げるときに、くっつく面の数は同じでなければならない。
このとき、直方体の側面の数の和の最大値はいくつか。
n≦10000とする。
解法
サイコロを積み上げる順番は関係がない。
一番下のサイコロの向きを1つ決めてやれば、残りのサイコロの向きは一意に決まる。
よって一番下のサイコロの向きを24通り試せばよい。
ソースコード
int pr[]={5,3,4,1,2,0}; int n,f[10000][6]; int main() { int cs; scanf("%d",&cs); while(cs--) { scanf("%d",&n); rep(i,n)rep(j,6)scanf("%d",f[i]+j); int ans=0; rep(t,6) { int sum=0,top=f[0][t]; rep(i,n) { int t=0,ntop; rep(j,6)if(f[i][pr[j]]==top) { ntop=f[i][j]; break; } rep(j,6)if(f[i][j]!=top&&f[i][j]!=ntop)t=max(t,f[i][j]); sum+=t; top=ntop; } ans=max(ans,sum); } printf("%d\n",ans); } return 0; }
1959 Darts
問題概要
ダーツの得点は的の当たった場所に応じて以下のようにつく。
- 1点〜20点のsliceはそのまま1〜20の点数
- doubleは1〜20の点数の2倍
- trebleは1〜20の点数の3倍
- Bull（中心）は25点
- Bull's eye（中心の中心）は50点
3投の点数の合計が競技の得点となる。
競技の得点が与えられたとき、その得点になるようなダーツの的中の仕方の組み合わせの数を求めよ。
解法
動的計画法の典型問。
dp[i][j][k]にi投目で、これまでの最高得点がj、合計得点がkであるような組み合わせの数をもち、漸化式にしたがい更新する。
ソースコード
vi pt; int dp[4][63][181],ans[181]; int main() { for(int i=1;i<=20;i++) { pt.pb(i); pt.pb(i*2); pt.pb(i*3); } pt.pb(0); pt.pb(25); pt.pb(50); sort(all(pt)); dp[0][0][0]=1; rep(i,3) { rep(j,63)rep(k,181)if(dp[i][j][k]) for(int l=j;l<63;l++) dp[i+1][l][k+pt[l]]+=dp[i][j][k]; } rep(j,63)rep(k,181) ans[k]+=dp[3][j][k]; int CS; scanf("%d",&CS); rep(cs,CS) { int p; scanf("%d",&p); printf("Scenario #%d:\n",cs+1); printf("%d\n\n",ans[p]); } return 0; }
1929 Calories from Fat
問題概要
脂肪、蛋白質、糖質、澱粉、アルコールはそれぞれ1グラムあたり9,4,4,4,7カロリーの熱量をもつ。
一日のそれぞれの摂取量が下のようなリストにより与えられたとき、
3g 10g 10% 0g 0g
リストの全ての日に摂取した熱量の合計のうち、脂肪によるものの割合を%で出力せよ。
摂取量の単位はg,%,Cのいずれかであり、5つのうちいずれかは%ではないことが保証されている。
解法
%以外を合計して(100-%)で割ると全体のカロリーがでる。
そこから%のところのカロリーは計算できる。
後は足して割って割合を求めればよい。
ソースコード
int r[]={9,4,4,4,7}; int main() { char in[99]; while(gets(in),strcmp(in,"-")) { double c[5]={0}; do{ int v[5]; char u[5]; sscanf(in,"%d%c %d%c %d%c %d%c %d%c", v,u,v+1,u+1,v+2,u+2,v+3,u+3,v+4,u+4); int pcnt=0; double sum=0; rep(i,5) { if(u[i]=='%')pcnt+=v[i]; else if(u[i]=='g')sum+=v[i]*r[i]; else sum+=v[i]; } sum/=(100-pcnt)/100.0; rep(i,5) { if(u[i]=='%')c[i]+=sum*v[i]/100; else if(u[i]=='g')c[i]+=v[i]*r[i]; else c[i]+=v[i]; } }while(gets(in),strcmp(in,"-")); printf("%.0f%%\n",c[0]/accumulate(c,c+5,0.0)*100); } return 0; }
1906 Expanding Rods
問題概要
長さLで熱膨張率Cの金属は温度がn度上がるとL'=(1+nC)Lの長さになる。
いま、L,C,nが与えられる。
はじめ金属はまっすぐの状態であり、加熱されると円弧の形になる。
円弧の高さを求めよ。
解法
円弧の中心角を2θ、円弧の半径をrなどとおけば、
2rθ=kL
2rsinθ=L
のような関係式が立ち(ただし1+nC=kとした)、
これらからsinθ/θ=1/kが得られ、二分法によりθの値が求まる。
θが求まれば、円弧の高さは(1-cosθ)kL/2θであるので答えが出る。
初めWAの原因が誤差死だと思ったらwhile文の条件をL>=0ではなくL>0にしてたのが原因だったorzあたまわるいぽorz
ソースコード
ld l,n,c; int main() { while(cin>>l>>n>>c,l>=0) { c=1+n*c; ld lo=0,hi=PI,mid; while(abs(hi-lo)>EPS) { mid=(lo+hi)/2; ld x=sin(mid)/mid; if(x>1/c)lo=mid; else hi=mid; } printf("%.3f\n",(double)((1-cos(hi))*c*l/hi/2)); } return 0; }
1961 Period
問題概要
長さNの文字列が与えられる。この文字列の長さi（2≦i≦N）の接頭辞が繰り返し文字列（同じ文字列がK＞1回以上繰り返してできた文字列）のような全てのiについて、
i,Kをiに関する昇順で出力せよ。
N≦1000000とする。
解法
KMP(Knuth Morris Prattというオートマトンを使ったパターンマッチングのアルゴリズム）を使うと接頭辞の繰り返しの検出ができるらしい。
そもそもKMPの構築方法から理解してないので解説はなし。
spaghetti sourceのKMPの解説（http://www.prefield.com/algorithm/string/knuth_morris_pratt.html）は微妙に間違っている気がする。
n-fail[n-1]ではなくてn-fail[n]が正しい。
ソースコード
int n; char in[1000001]; int fail[1000001]; int main() { int cs=0; while(scanf("%d",&n),n) { scanf("%s",in); int j=fail[0]=-1; for(int i=1;i<=n;i++) { while(j>=0&&in[j]!=in[i-1])j=fail[j]; fail[i]=++j; } printf("Test case #%d\n",++cs); for(int i=1;i<=n;i++) { int len=i-fail[i]; if(i==len||i%len)continue; printf("%d %d\n",i,i/len); } puts(""); } return 0; }
