PKU演習問メモ(8/29)
解説まとめる気力が出ない。後でかく。←かいた。日に日に適当になる。
| No. | 問題名 | 問題の種類および解法 | 難易度 |
|---|---|---|---|
| 3386 | Halloween Holidays | 幾何 | ★★☆☆☆ |
| 2676 | Sudoku | 探索 | ★★★☆☆ |
| 2587 | Airline Hub | 幾何 | ★★☆☆☆ |
| 2555 | Drink, on Ice | 実装 | ★★★☆☆ |
| 2584 | T-Shirt Gumbo | 最大流 | ★★★☆☆ |
| 2567 | Code the Tree | 構文解析・グラフ | ★★★☆☆ |
| 2508 | Conic distance | 幾何 | ★★☆☆☆ |
3386 Halloween Holidays
問題概要
半径Pの円盤から、外側の半径A,内側の半径aのリングおよび外側の半径B,内側の半径bのリングの二つが切り取れるかどうか判定せよ。
解法
やたらWAが多いので難しいのかと思ったらみんな問題文を読み違えているようだった。
可能な切り取り方は、小さいリングが大きいリングの内部にある場合、または大きいリングの外に小さいリングがある場合の二通り。
ソースコード
int main() { int A,a,B,b,P; scanf("%d%d%d%d%d",&A,&a,&B,&b,&P); if(A>P||B>P); else if(b>=A||a>=B||A+B<=P) { puts("Yes"); return 0; } puts("No"); return 0; }
2676 Sudoku
問題概要
与えられた数独の盤面を解け。（0のマスが空白を表す）
答えが複数個ある場合どれを出力してもかまわない。
ソースコード
char bd[9][10]; int row[9],col[9],box[9]; bool dfs() { int mi=-1,mj=-1,mn=10,mnt; rep(i,9)rep(j,9)if(bd[i][j]=='0') { int c=0,t=(1<<9)-1&~row[i]&~col[j]&~box[i/3*3+j/3]; for(int b=t;b;b=(b-1)&b)c++; if(mn>c)mn=c,mi=i,mj=j,mnt=t; } if(mi<0)return 1; rep(i,9)if(1<<i&mnt) { bd[mi][mj]='1'+i; row[mi]^=1<<i; col[mj]^=1<<i; box[mi/3*3+mj/3]^=1<<i; if(dfs())return 1; bd[mi][mj]='0'; row[mi]^=1<<i; col[mj]^=1<<i; box[mi/3*3+mj/3]^=1<<i; } return 0; } int main() { int cs; scanf("%d",&cs); while(cs--) { rep(i,9)scanf("%s",bd[i]); rep(i,9)row[i]=col[i]=box[i]=0; rep(i,9)rep(j,9)if(bd[i][j]!='0') { int b=1<<bd[i][j]-'1'; row[i]|=b; col[j]|=b; box[i/3*3+j/3]|=b; } dfs(); rep(i,9)puts(bd[i]); } return 0; }
2587 Airline Hub
解法
球面三角法を使ったらWAで、まさかの直線距離を使うらしい。
どこの国のAirlineが地中をまっすぐ結ぶんだ？なめやがって。クソ問認定。
ソースコード
int n; double la[1000],lo[1000],X[1000],Y[1000],Z[1000]; double d[1000][1000],mxd[1000]; /* dist(la[i],la[j],abs(lo[i]-lo[j])) double dist(double p1,double p2,double dl) { if(dl>PI)dl=2*PI-dl; return acos(sin(p1)*sin(p2)+cos(p1)*cos(p2)*cos(dl)); } */ double sq(double a) { return a*a; } int main() { scanf("%d",&n); rep(i,n)scanf("%lf%lf",la+i,lo+i),la[i]*=PI/180,lo[i]*=PI/180; rep(i,n) { X[i]=cos(lo[i])*cos(la[i]); Y[i]=sin(lo[i])*cos(la[i]); Z[i]=sin(la[i]); } rep(i,n) { d[i][i]=0; rep(j,i)d[i][j]=d[j][i]=sq(X[i]-X[j])+sq(Y[i]-Y[j])+sq(Z[i]-Z[j]); } rep(i,n) { double mx=0; rep(j,n)mx=max(mx,d[i][j]); mxd[i]=mx; } double mn=INF; int mni=0; rep(i,n)if(mxd[i]<mn)mn=mxd[i],mni=i; printf("%.2f %.2f\n",la[mni]*180/PI,lo[mni]*180/PI); return 0; }
2555 Drink, on Ice
問題概要
水と氷の比熱および溶解熱が与えられる。
温度tiのmwグラムの水と温度tcでmcグラムの氷を外部と熱のやりとりのない容器に混ぜて、十分な時間を置いたときの、水・氷の量、および系の温度を求めよ。
解法
コード参照。符号に十分気をつける。
ソースコード
const double cw=4.19,ci=2.09,em=335; int main() { double mw,mi,tw,ti; while(scanf("%lf%lf%lf%lf",&mw,&mi,&tw,&ti),mw||mi||tw||ti) { double ice=-mi*ti*ci,water=mw*tw*cw; double tokeru=mi*em,kooru=mw*em; if(ice+tokeru<water) { double tmp=water-(ice+tokeru); tmp/=(mi+mw)*cw; printf("0.0 g of ice and %.1f g of water at %.1f C\n", mi+mw,tmp); } else if(ice>water+kooru) { double tmp=ice-(water+kooru); tmp/=(mi+mw)*ci; printf("%.1f g of ice and 0.0 g of water at %.1f C\n", mi+mw,-tmp); } else { double de=ice-water; mi+=de/em,mw-=de/em; printf("%.1f g of ice and %.1f g of water at 0.0 C\n", mi,mw); } } return 0; }
2584 T-Shirt Gumbo
問題概要
5種類のサイズのシャツの、それぞれの枚数が与えられる。
n人の人間の、各自が着られるサイズが与えられるとき、全員が着られるサイズのシャツを受け取ることが可能かどうか判定せよ。
解法
それぞれのシャツを湧き出し、各人を吸い込みとしたネットワークグラフをつくる。
シャツの湧き出しの量は、そのシャツの枚数に等しく、人の吸い込みは1にする。
着られるシャツと人を辺で結んで（ここの容量はなんでもいい。下のソースでは1）、フローを流せば、その最大フローが最大のシャツの分配枚数になる。
ソースコード
char size[256]; int main() { size['S']=0; size['M']=1; size['L']=2; size['X']=3; size['T']=4; char str[20]; while(scanf("%s",str),str[0]=='S') { int n; scanf("%d",&n); Graph g(n+7); rep(i,n) { g[i+6].pb(Edge(i+6,n+6,1)); g[n+6].pb(Edge(n+6,i+6,0)); scanf("%s",str); int a=size[str[0]],b=size[str[1]]; for(int j=a;j<=b;j++) g[j+1].pb(Edge(j+1,i+6,1)),g[i+6].pb(Edge(i+6,j+1,0)); } rep(i,5) { int t; scanf("%d",&t); g[0].pb(Edge(0,i+1,t)); g[i+1].pb(Edge(i+1,0,0)); } int ans=maximumFlow(g,0,n+6); puts(ans==n?"T-shirts rock!":"I'd rather not wear a shirt anyway..."); scanf("%s",str); } return 0; }
2567 Code the Tree
問題概要
木のグラフが括弧を使った式で表される。
この木に対して、「一番番号の小さな葉のノードを取り、その親の番号を出力する」という操作を、ノードがひとつになるまで繰り返せ。
解法
括弧を使った式を構文解析して隣接行列のグラフを作る。
あとはpriority_queueなどを使うなりして、適当に頂点を削除する。（コード参照）
ソースコード
bool e[50][50]; int deg[50]; char str[500]; int toi(int s,int t) { int ret=0; for(;s<t;s++)if(isdigit(str[s]))ret*=10,ret+=str[s]-'0'; return ret; } void eval(int s,int t,int pa) { while(s<t&&str[s]==' ')s++; while(s<t&&str[t-1]==' ')t--; if(s>=t)return; int p,q,d,a; for(p=s+1;p<t;p++)if(str[p]=='('||str[p]==')')break; a=toi(s,p)-1; if(pa>=0)e[pa][a]=e[a][pa]=1; for(q=s,d=0;q<t;q++) { if(str[q]=='(')d++; if(str[q]==')')d--; if(d==0)break; } eval(p,q,a); eval(q+1,t,pa); } int main() { while(gets(str)) { rep(i,50)rep(j,50)e[i][j]=0; eval(0,strlen(str),-1); rep(i,50)deg[i]=0; rep(i,50)rep(j,50)if(e[i][j])deg[i]++; priority_queue<int> Q; rep(i,50)if(deg[i]==1)Q.push(-i); int t=0,ans[50]; while(!Q.empty()) { int k=-Q.top(),p=0; Q.pop(); for(;p<50;p++)if(e[k][p])break; if(p==50)break; ans[t++]=p+1; rep(i,50)if(e[i][k]) { deg[i]--; e[i][k]=e[k][i]=0; if(deg[i]==1)Q.push(-i); } } rep(i,t) { if(i)putchar(' '); printf("%d",ans[i]); } puts(""); } return 0; }
2508 Conic distance
問題概要
xy平面に半径r,中心原点の円の底面をもち、高さがhであるような円錐がある。
この円錐（側面の）表面上の二点が、その頂点からの距離および真上からみたときのx軸とのなす角度により与えられる。
円錐の（側面の）表面を通り、二点を結ぶ最短距離を求めよ。
解法
展開図の二点を結ぶ直線が求める距離。
ソースコード
int main() { double r,h,d1,a1,d2,a2; while(~scanf("%lf%lf%lf%lf%lf%lf",&r,&h,&d1,&a1,&d2,&a2)) { double a=hypot(r,h),t2=2*PI*r/a,t1=abs(a1-a2)*PI/180*r/a; double x=d2*cos(t1),y=d2*sin(t1),X=d1*cos(t2),Y=d1*sin(t2); double ans=min(hypot(x-d1,y),hypot(x-X,y-Y)); printf("%.2f\n",ans); } return 0; }
