PKU演習問メモ(9/15)
| No. | 問題名 | 問題の種類および解法 | 難易度 |
|---|---|---|---|
| 2722 | Angle and Squares | 幾何 | ★★☆☆☆ |
| 1130 | Alien Security | 深さ優先探索・幅優先探索 | ★★☆☆☆ |
| 1035 | Spell checker | 文字列 | ★★☆☆☆ |
| 1129 | Channel Allocation | グラフの頂点彩色 | ★★★☆☆ |
| 1034 | The dog task | 二部グラフの最大マッチング | ★★★☆☆ |
| 1027 | The Same Game | 実装 | ★★☆☆☆ |
2722 Angle and Squares
問題概要
第一象限内に二点A,Bがある。
各辺が座標軸に平行なn個の正方形を第一象限内で動かし、半直線OAおよびOBとn個の正方形で囲まれた図形の面積を最大にしたい。
A,Bの座標および各正方形の一辺の長さが与えられた時、このような面積を求めよ。
解法
囲まれる部分の面積が最大になるのは正方形が
■ ■ ■
のようにぴったり斜めに並ぶとき。
したがってそのような並び方をするときの直線との接点を求め、次いで内部の面積を求めてやればよい。
斜めに並んだ正方形の、左上・右下の頂点は全てy=-x+k上にあるので、
座標平面上の直線の交点P,Qを求め、PQが正方形の対角線の長さの和になるよう適当にkを動かす。
ソースコード
int n; double ax,ay,bx,by,l[15]; int main() { while(scanf("%d",&n),n) { double p,q,r,s; scanf("%lf%lf%lf%lf",&p,&q,&r,&s); q/=p; s/=r; ax=1.0/(q+1); ay=1-ax; bx=1.0/(s+1); by=1-bx; rep(i,n)scanf("%lf",l+i); double d,sum=0,m,ans; d=hypot(ax-bx,ay-by); rep(i,n)sum+=l[i]; sum*=sqrt(2.0); m=sum/d; ax*=m; ay*=m; bx*=m; by*=m; ans=abs(ax*by-ay*bx); rep(i,n)ans-=l[i]*l[i]; ans/=2; printf("%.3f\n",ans); } return 0; }
1130 Alien Security
問題概要
各部屋のつながりが有向グラフで表される、部屋数nの研究所が与えられる。
この研究所の部屋eには宇宙人がいる。
セキュリティの為、0番の部屋から出発して宇宙人の部屋に行くにはどうやってもガードマンを通さねばならないようにしたい。
ただしそのような部屋のなかで宇宙人の部屋からもっとも近い場所にガードマンを（一人だけ）配置したい。
そのような部屋の番号を出力せよ。ただし宇宙人の部屋にはガードマンを置くことはできないものとする。
解法
入力をEOFまでではなく何故かn回までしか取ってなくて2WAorz
nの値の範囲が問題文で与えられていないが、100くらいでも通る模様。
ガードマンの人数は一人であるので、ガードマンを置く部屋を全てn通り試せばよい。
それぞれに対してガードマンの部屋を通らないで宇宙人の部屋へいけるかどうか深さ優先探索で求める。
あとはそのような候補の中で、最も宇宙人の部屋から近い部屋を幅優先探索により求めればよい。
ソースコード
int n,et; vector<vi> e,re; bool from0[1000],v[1000]; int d[1000]; bool dfs(int c) { v[c]=1; if(c==et)return 1; fr(i,e[c])if(!v[*i]&&dfs(*i))return 1; return 0; } int main() { scanf("%d%d",&n,&et); e.resize(n); re.resize(n); int a,b; while(~scanf("%d%d",&a,&b))e[a].pb(b),re[b].pb(a); rep(i,n)d[i]=inf; d[et]=0; queue<int> Q; Q.push(et); while(!Q.empty()) { int c=Q.front(); Q.pop(); fr(i,re[c])if(d[*i]>d[c]+1) d[*i]=d[c]+1,Q.push(*i); } Q.push(0); from0[0]=1; while(!Q.empty()) { int c=Q.front(); Q.pop(); fr(i,e[c])if(!from0[*i]) from0[*i]=1,Q.push(*i); } pi cand[1000]; int nc=0; rep(i,n)if(d[i]!=inf&&from0[i]&&i!=et)cand[nc++]=mp(d[i],i); sort(cand,cand+nc); rep(i,nc) { int c=cand[i].second; rep(j,n)v[j]=0; v[c]=1; if(c==0||!dfs(0)) { printf("Put guards in room %d.\n",c); break; } } return 0; }
1035 Spell checker
問題概要
辞書に登録された単語を元に、入力された単語の正誤を判定するスペルチェッカー作りたい。
入力された単語が辞書にある場合、"X is correct"を、
存在しない場合、正しい単語の候補を、辞書に登録された順に全て出力せよ。
ただし、正しい単語の候補とは、
- 一字を別の好きな一字に変える
- 一字を削除する
- 好きな一字を挿入する
の操作をどれか１度だけ行って、入力された単語に変換できるものを言う。
辞書の単語の数は10000以下、各単語の文字数は50字以下である。
解法
辞書に登録された順に候補を出力しなければならないので、辞書は線形リストのような形で持つのが自然である。（入力の順序を覚えておいて、出力をそれに基づいてソートすることも考えられるが）
与えられた単語の入力に対して、辞書のそれぞれの文字にマッチするかを見ていく。
変更・削除・挿入の操作は1回しか行われないのでO(長さ)の時間でマッチができる。
ソースコード
int n,len[10000]; char dic[10000][51],wd[51]; int out[10000],no; int ok(int d) { int l=strlen(wd); if(abs(len[d]-l)>1)return 0; if(len[d]==l) { int cnt=0; rep(i,l)if(dic[d][i]!=wd[i])cnt++; return cnt==0?2:cnt<=1; } if(len[d]==l+1) { int i=0,j=0; for(;i<l+1;i++)if(dic[d][i]==wd[j])j++; return j==l; } if(len[d]+1==l) { int i=0,j=0; for(;i<l;i++)if(dic[d][j]==wd[i])j++; return j==l-1; } } int main() { while(gets(dic[n]),dic[n][0]!='#')len[n]=strlen(dic[n++]); while(gets(wd),wd[0]!='#') { printf("%s",wd); bool f=0; no=0; rep(i,n) { int res=ok(i); if(res==0); else if(res==1)out[no++]=i; else { f=1; no=0; break; } } if(f)printf(" is correct"); else putchar(':'); rep(i,no)printf(" %s",dic[out[i]]); puts(""); } return 0; }
1129 Channel Allocation
問題概要
n個の、英大文字一字で表されるラジオ局がある。
このラジオ局は、電波が干渉する範囲では異なる波長の電波を使う必要がある。
しかし、使用する電波の帯域はなるべく小さくする必要がある。
電波の干渉するラジオ局のリストが与えられたとき、使う電波の波長の数の最小値を求めよ。
解法
一般グラフの頂点彩色問題なのでNP完全だったか、NP困難だったか。
（多項式時間では解けないと思われるクラス）
が、この問題ではサイズが小さいので力づくの探索で解ける。
色数n色でグラフの頂点を塗れるかどうかをの関数がdfs（深さ優先探索で塗り方を全て試している）
これを全てのnの候補iについて（1≦i≦nで十分）試せばよい。
ソースコード
int n,color[26]; bool e[26][26]; bool ck(int c) { rep(i,c)if(e[c][i]&&color[c]==color[i])return 0; return 1; } bool dfs(int c,int col) { if(c==n)return 1; for(int i=1;i<=col;i++) { color[c]=i; if(ck(c)&&dfs(c+1,col))return 1; color[c]=0; } return 0; } int main() { while(scanf("%d ",&n),n) { rep(i,n)rep(j,n)e[i][j]=0; rep(i,n) { char in[30]; gets(in); for(int j=2;in[j];j++) { int a=in[0]-'A',b=in[j]-'A'; e[a][b]=e[b][a]=1; } } int ans=1; for(;ans<=n;ans++) { rep(i,n)color[i]=0; if(dfs(0,ans))break; } printf("%d channel%s needed.\n",ans,ans>1?"s":""); } return 0; }
1034 The dog task
問題概要
Bobが犬を連れて散歩する。
Bobの散歩の経路は折れ線(x1,y1),(x2,y2),……,(xn,yn)により与えられる。
犬はBobが(xi,yi),(xi+1,yi+1)に移動する間、Bobを離れて自分の遊び場(x'j,y'j)を最大一つだけ訪問し、(xi+1,yi+1)で合流する。
犬の走る速度はBobの速度の2倍以下であり、犬は同じ遊び場を1度しか訪れない。
Bobの散歩道(xi,yi)および遊び場の座標(x'j,y'j)が与えられた時、犬が訪れることのできる遊び場の数を最大にするような、犬の散歩道を求めよ。
n,m（遊び場の数）≦100を満たす。
解法
二部グラフの最大マッチングの典型問（たぶん？）
折れ線の各線分について一ヶ所しか遊び場を訪れられず、かつ遊び場は一度しか訪れられないので、
- 折れ線のそれぞれの線分を赤いノード
- 遊び場を青いノード
とした二部グラフを作り、最大マッチングを行えばよい。
エッジをつなぐのは、Bobがその線分を移動する間に犬が行って帰ってこられる場合（距離が線分の2倍以下）である。
ソースコード
int n,m; vector<vi> e; int p[200]; bool v[200]; bool match(int s) { if(s<0)return 1; fr(i,e[s])if(!v[*i]) { v[*i]=1; if(match(p[*i]))return p[s]=*i,p[*i]=s,1; } return 0; } int main() { scanf("%d%d",&n,&m); e.resize(n+m); int x[100],y[100],X[100],Y[100]; rep(i,n)scanf("%d%d",x+i,y+i); rep(i,m)scanf("%d%d",X+i,Y+i); rep(i,n-1) { double d=2*hypot(x[i]-x[i+1],y[i]-y[i+1]); rep(j,m)if(hypot(x[i]-X[j],y[i]-Y[j])+hypot(x[i+1]-X[j],y[i+1]-Y[j])<=d) e[i].pb(j+n),e[j+n].pb(i); } int k=0; rep(i,n+m)p[i]=-1; rep(i,n-1) { rep(j,n+m)v[j]=0; if(match(i))k++; } printf("%d\n",k+n); rep(i,n) { if(i)putchar(' '); printf("%d %d",x[i],y[i]); if(p[i]>=0)printf(" %d %d",X[p[i]-n],Y[p[i]-n]); } puts(""); return 0; }
1027 The Same Game
問題概要
さめがめという一人用ゲームがある。
10x15のグリッドが初めRGB三色の駒で埋め尽くされている。盤面において同色の駒が2つ以上連結している場所を「クラスタ」と呼ぶ。
プレイヤーは好きなクラスタを選び、それを消去することができる。
消された駒の上の乗っていた駒は地面または下の駒まで落下する。
消去によって一列（以上）が空になった場合、その列は左へ詰められる。
さめがめの初期盤面が与えられたとき、最もサイズの大きいクラスタから消去していく戦略でさめがめをプレイする。これをシミュレートせよ。
同じサイズのクラスタが複数あるときは、最も左にあるものを、それでも複数ある場合その中で最も下にあるものを選ぶものとする。
解法
same gameで同じゲーム？なんのこっちゃ、とか思ってたらさめがめのことらしい。
……と言うかそもそもさめがめの名前の由来が同じものを消すことから「same game」だったらしい。
DFSでクラスタのサイズを数えて、大きいところを消せばいい。
消えたところを詰める処理は沢山ループを回してナイーブにやってよい。
ソースコード
int dy[]={-1,0,1,0},dx[]={0,-1,0,1}; const int h=10,w=15; char in[20][20]; bool v[20][20]; int nul(int y,int x,char c,bool er) { if(er)in[y][x]=0; else v[y][x]=1; int ret=1; rep(d,4) { int ny=y+dy[d],nx=x+dx[d]; if(ny<0||ny>=h||nx<0||nx>=w||in[ny][nx]!=c)continue; if(er||!v[ny][nx])ret+=nul(ny,nx,c,er); } return ret; } int main() { int CS; scanf("%d",&CS); rep(cs,CS) { rep(i,h)scanf("%s",in[h-1-i]); printf("Game %d:\n\n",cs+1); int n=h*w,sc=0,mv=0; while(n>0) { int mx=1,mi,mj; rep(i,h)rep(j,w)v[i][j]=0; rep(j,w)rep(i,h)if(in[i][j]&&!v[i][j]) { int c=nul(i,j,in[i][j],0); if(c>mx)mx=c,mi=i,mj=j; } if(mx==1)break; printf("Move %d at (%d,%d): removed %d balls of color %c, got %d points.\n", ++mv,mi+1,mj+1,mx,in[mi][mj],(mx-2)*(mx-2)); n-=mx; sc+=(mx-2)*(mx-2); nul(mi,mj,in[mi][mj],1); rep(j,w)for(int i=1;i<h;i++)if(in[i][j]) for(int k=i;k>0&&in[k-1][j]==0;k--)swap(in[k][j],in[k-1][j]); for(int j=w-1;j>=0;j--) { rep(i,h)if(in[i][j])goto SKIP; for(int x=j+1;x<w;x++)rep(i,h)swap(in[i][x],in[i][x-1]); SKIP:; } } if(n==0)sc+=1000; printf("Final score: %d, with %d balls remaining.\n\n",sc,n); } return 0; }
