PKU演習問メモ(6/24)
| No. | 問題名 | 問題の種類および解法 | 難易度 |
|---|---|---|---|
| 1131 | Octal Fractions | 多倍長小数演算 | ★★☆☆☆ |
| 2435 | Navigating the City | ダイクストラ+経路出力 | ★★★☆☆ |
| 1556 | The Doors | 幾何+ダイクストラ | ★★★☆☆ |
| 3267 | The Cow Lexicon | 動的計画法 | ★★☆☆☆ |
| 2044 | Weather Forecast | 枝刈り探索 | ★★★★☆ |
1131 Octal Fractions
問題概要
与えられた8進数の小数を10進数の小数へと変換せよ。
解法
任意精度が求められるので、Javaの人はBigDecimalを使う。
C++の人は多倍長演算を自分で実装する。
ソースコード
import java.math.*; import java.util.*; class Main { public static void main(String[] args) { new Main().new pku1131().run(); } class pku1131{ void run(){ String s=new String(); Scanner sc=new Scanner(System.in); while(sc.hasNext()){ s=sc.next(); BigDecimal ans=new BigDecimal(0); BigDecimal now=new BigDecimal(1); for(int i=2;i<s.length();i++){ now=now.divide(BigDecimal.valueOf(8)); ans=ans.add(now.multiply(BigDecimal.valueOf((int)(s.charAt(i)-'0')))); } System.out.print(s); System.out.print(" [8] = "); System.out.print(ans); System.out.println(" [10]"); } } } }
2435 Navigating the City
問題概要
横n本縦e本の路地からなる町をSからEまで最短経路で移動したい。
そのような経路を指定されたフォーマットで出力せよ。
最短経路は一意に定まることが保証されている。
n≦30,e≦40である。
解法
解法はダイクストラ法を用いればよいがやや実装量が多いので★三つ。
経路出力は、それぞれのマスに対して自分の移動元の座標を覚えればゴールから辿って経路を復元できるので、それを実装する。
座標はあらかじめ倍にしておくと楽（？）。
ソースコード
int dy[]={-1,0,1,0},dx[]={0,1,0,-1}; int n,e,sy,sx,ey,ex; char str[100][100]; int cost[100][100],py[100][100],px[100][100]; bool valid(int y,int x) { if(y<0||x<0||y>=n||x>=e)return 0; if(str[y][x]=='.')return 0; return 1; } int main() { cin>>n>>e; n=n*2-1; e=e*2-1; rep(i,n) { cin>>str[i]; rep(j,e) { if(str[i][j]=='S')sy=i,sx=j,str[i][j]='+'; if(str[i][j]=='E')ey=i,ex=j,str[i][j]='+'; } fill_n(cost[i],e,inf); } cost[sy][sx]=0; priority_queue<pair<int,pi> > Q; Q.push(mp(0,mp(sy,sx))); while(!Q.empty()) { int cy=Q.top().second.first,cx=Q.top().second.second; int cc=Q.top().first; Q.pop(); if(cost[cy][cx]<-cc)continue; if(cy==ey&&cx==ex)break; rep(d,4) { int ny=cy+dy[d],nx=cx+dx[d],nc=cc; while(valid(ny,nx)&&str[ny][nx]!='+')ny+=dy[d],nx+=dx[d],nc--; if(!valid(ny,nx)||str[ny][nx]!='+')continue; if(cost[ny][nx]<=-nc)continue; cost[ny][nx]=-nc; py[ny][nx]=cy; px[ny][nx]=cx; Q.push(mp(nc,mp(ny,nx))); } } int dis[2000],step=0; char dir[2000]; for(int y=ey,x=ex;!(y==sy&&x==sx);) { int ny=py[y][x],nx=px[y][x]; dis[step]=cost[y][x]-cost[ny][nx]; char &c=dir[step]; if(ny-y==0)c=nx<x?'E':'W'; else { assert(nx-x==0); c=ny<y?'S':'N'; } y=ny,x=nx; if(step>0&&dir[step-1]==c)dis[step-1]+=dis[step]; else step++; } for(int i=step-1;i>=0;i--)cout<<dir[i]<<" "<<dis[i]<<endl; return 0; }
1556 The Doors
問題概要
座標平面上の(0,0)と(10,10)をその二隅とするような、各辺が座標軸に平行な正方形の部屋を考える。
この部屋にはいくつか仕切りがあり、それらの座標が与えられる。このとき、(0,5)から(10,5)まで仕切りを避けながら最短距離で移動するときの移動距離を求めよ。
解法
仕切りは線分として情報を持っておく。
スタートの点・ゴールの点・仕切りの両端をノードとするダイクストラ法を行えばよい。
点から点への移動が仕切りの線分と重なるならその移動はできない。
その判定は下のコードのような線形探索で十分間に合う。
ソースコード
線分の交差判定でSpaghetti Sourceのコードを使用（その部分は省略）
typedef complex<double> P; int n,np,ns; vector<L> seg; vector<P> pt; bool visible(int a,int b) { L line(pt[a],pt[b]); rep(i,ns) { rep(j,2)rep(k,2)if(line[j]==seg[i][k])goto SKIP; if(intersectSS(line,seg[i]))return 0; SKIP:; } return 1; } int main() { while(cin>>n,~n) { seg.clear(); pt.clear(); pt.pb(P(0,5)); pt.pb(P(10,5)); cin.ignore(); rep(i,n) { string str; getline(cin,str); stringstream ss(str); double x,y,prev=0; ss>>x; int cnt=0; while(ss>>y) { pt.pb(P(x,y)); if(cnt++%2==0)seg.pb(L(P(x,prev),P(x,y))); prev=y; } seg.pb(L(P(x,prev),P(x,10))); } np=pt.size(),ns=seg.size(); vector<double> cost(np,inf); cost[0]=0; priority_queue<pair<double,int> > Q; Q.push(mp(0,0)); while(!Q.empty()) { int c=Q.top().second; double cc=Q.top().first; Q.pop(); if(cost[c]<-cc)continue; if(c==1) { printf("%.2f\n",-cc); break; } rep(i,np)if(visible(c,i)) { double nc=cc-abs(pt[c]-pt[i]); if(cost[i]>-nc)cost[i]=-nc,Q.push(mp(nc,i)); } } } return 0; }
3267 The Cow Lexicon
問題概要
l文字の文字列および、w個の単語からなる辞書が与えられる。
l文字の文字列を、辞書の単語をいくつか並べたものの間に何文字かの"ノイズ"が入ったものとみなすとき、ノイズとしてありうる最小の文字数を求めよ。
l≦300,w≦600を満たす。
解法
文字列のi文字目までの"ノイズ"の値の最小値をdp[i]としてもっておけば、
文字列のi+1文字目から辞書の単語を全て探索することで先のdpの配列を更新できる。
探索は下のfind関数のようなナイーブなもので間に合う。
ソースコード
int w,l,len[600]; char word[301],dic[600][301]; int dp[301]; int find(int id,int s) { for(int cur=0;s<l;s++) { if(dic[id][cur]==word[s])cur++; if(cur==len[id])return s+1; } return inf; } int main() { scanf("%d%d",&w,&l); scanf("%s",word); rep(i,w)scanf("%s",dic[i]),len[i]=strlen(dic[i]); fill_n(dp,301,inf); dp[0]=0; for(int i=1;i<=l;i++) { rep(j,w) { int p=find(j,i-1); if(p==inf)continue; dp[p]=min(dp[p],dp[i-1]+p-i+1-len[j]); } } int ans=inf; rep(i,l+1)ans=min(ans,l-i+dp[i]); printf("%d\n",ans); return 0; }
2044 Weather Forecast
問題概要
4x4のグリッドで表される国があり、そこ2x2の雲を動かしてn日の間雨を降らせる。
雲は各一日の最初に上下左右のいずれかの方向に1マスまたは2マス動かす、あるいは全く動かさないこともできる。
ただし、第一日目の位置は中央でなければならない。
各グリッドについて毎日市場が開催されるかどうかが与えられ、市場の開催される日にそのグリッドに雨を降らせてはいけない。また、7日間連続して雨が降らないグリッドがあってもならない。
このとき、n日の間無事に雨を降らすことができるなら1を、そうでないなら0を出力せよ。
n≦365とする。
解法
雲の動かし方の総数は5^nなので総当りでは解けない。
メモ化探索もそのままでは状態数が多く不可能である。
そこで以下のような枝刈りをする。
左上のマスに雨が降るとき、その周囲の3マスにも必ず雨が降る。右上、左下、右下のマスについても同様のことがいえる。
すなわち、16マスのいずれかのマスに7日間雨が降らないことは端のいずれかの4マスに7日間雨が降らないということと同値である。
したがって状態として持つのは四隅の雨の降っていない日数のみでよい。
これを実装したのが以下。（結構綺麗）
ソースコード
int n; bool market[365][16]; bool V[366][2401][9]; bool check(int day,int y,int x) { rep(i,2)rep(j,2)if(market[day][(y+i)*4+x+j])return 0; return 1; } bool visit(int day,int y,int x,int r0,int r1,int r2,int r3) { bool &v=V[day][343*r0+49*r1+7*r2+r3][y*3+x]; if(v)return 1; v=1; return 0; } bool dfs(int day,int cy,int cx,int r0,int r1,int r2,int r3) { if(day>=n)return 1; for(int ny=cy-2;ny<=cy+2;ny++)for(int nx=cx-2;nx<=cx+2;nx++) if(ny==cy||nx==cx) if(0<=ny&&ny<3&&0<=nx&&nx<3) { if(!check(day,ny,nx))continue; int nr0=r0,nr1=r1,nr2=r2,nr3=r3; if(ny==0&&nx==0)nr0=0; else nr0++; if(ny==0&&nx==2)nr1=0; else nr1++; if(ny==2&&nx==0)nr2=0; else nr2++; if(ny==2&&nx==2)nr3=0; else nr3++; if(nr0>=7||nr1>=7||nr2>=7||nr3>=7)continue; if(visit(day+1,ny,nx,nr0,nr1,nr2,nr3))continue; if(dfs(day+1,ny,nx,nr0,nr1,nr2,nr3))return 1; } return 0; } int main() { while(scanf("%d",&n),n) { rep(i,n)rep(j,16)scanf("%d",market[i]+j); rep(i,n+1)rep(j,2401)fill_n(V[i][j],9,0); if(!check(0,1,1)) { cout<<0<<endl; continue; } cout<<dfs(1,1,1,1,1,1,1)<<endl; } return 0; }
