PKU演習問メモ(4/9)
| No. | Title | 分類・解法 |
|---|---|---|
| 1469 | COURSES | Maximum matching in Bipartite graph |
| 1607 | Deck | Simple Math |
| 1782 | Run Length Encoding | String manipulation |
| 1724 | ROADS | Dijkstra's algorithm(extended) |
| 3435 | Sudoku Checker | Straight forward |
| 1088 | 滑雪 | Dynamic programming |
| 1323 | Game Prediction | Simple Math |
| 2664 | Prerequisites? | Straight forward |
| 2818 | Making Change | DFS |
| 1326 | Mileage Bank | Straight forward |
うーやばいやばいノルマ量があっぷあっぷorz
以下問題概要や解法など。
1469 COURSES
問題概要
p個の講義のn人の生徒があり、それぞれの生徒が取る講義のリストが与えられる。このとき
- 各講義を一人が代表する
- 各生徒が講義を一つ代表する
ような生徒の集合を取れるかどうか判定せよ。
解法
生徒と講義を二部グラフとみて最大マッチングを試み、講義の頂点全てに生徒の頂点をつなげられたかどうかを調べればよい。
辺の数は多いので隣接行列を使えばよい。入力にはscanfを使わないとTLEする。（したorz）
ソースコード
int p,n,e[400][400]; int pr[400]; bool V[400]; bool rec(int s) { if(s<0)return 1; for(int i=s<p?p:0;i<(s<p?p+n:p);i++)if(!V[i]&&e[s][i]){ V[i]=1; if(rec(pr[i]))return pr[i]=s,pr[s]=i,1; } return 0; } int main() { int cs; scanf("%d",&cs); while(cs--){ scanf("%d%d",&p,&n); rep(i,n+p){ rep(j,n+p)e[i][j]=0; pr[i]=-1; } rep(i,p){ int k,t; scanf("%d",&k); rep(j,k)scanf("%d",&t),e[t-1+p][i]=e[i][t-1+p]=1; } int cnt=0; rep(i,p){ fill(V,V+(n+p),0); V[i]=1; if(rec(i))cnt++; } cout<<(cnt==p?"YES":"NO")<<endl; } return 0; }
1607 Deck
問題概要
n枚のカードを積み重ねて机からできるだけはみ出すように置きたい。
nが与えられた時、机からはみ出すカードの長さを求めよ。
解法
有名問題。
n枚の重心の位置からn+1枚の重心の位置が求まる。
(x[n]*n + x[n] + 1/2)/(n+1) = x[n+1]
⇔x[n+1] = 1 / 2(n+1)
これを利用して足し算で答えを求めればよい。特にメモ化などをしなくとも計算時間の心配はない。出力の書式には注意。
ソースコード
int main() { int n; printf("Cards Overhang\n"); while(cin>>n) { double ans=0; for(int i=1;i<=n;i++)ans+=.5/i; printf("%5d %8.3f\n",n,ans); } return 0;
1782 Run Length Encoding
問題概要
簡単なRun Length Encodingについて考える。与えられた文字列に対して、
- 2-9文字の同一文字の連続がある場合、「文字の長さ+元の文字」に置き換える
- 同一文字が連続しないような文字が連続して現れた場合、その部分を「1+文字列+1」に置き換える。ただしその文字列中に1が出てきたら1は11に置き換える。
のような変換を施せ。
解法
getlineで一行ずつ文字を取得し、文字を一文字ずつ上の条件に適するかどうか調べて見ていけばよい。
ソースコード
int main() { string str; while(getline(cin,str)) { int len=str.size(); string ans; for(int i=0;i<len;) { int isuc=1; while(i+isuc<len&&isuc<9&&str[i]==str[i+isuc])isuc++; if(isuc!=1) { ans.pb('0'+isuc); ans.pb(str[i]); i+=isuc; continue; } int suc=1; while(i+suc<len&&(i+suc+1==len||str[i+suc]!=str[i+suc+1]))suc++; ans.pb('1'); rep(j,suc) { if(str[i+j]=='1')ans.pb('1'); ans.pb(str[i+j]); } ans.pb('1'); i+=suc; } cout<<ans<<endl; } return 0; }
1724 ROADS
問題概要
ボブとアリスは町1に住んでいたが、ボブはアリスが自分にカードゲームでイカサマを使っていたことに気づき、頭にきて町Nに引っ越すことにした。
しかしボブは金欠になってしまっているのでの通行料の合計がk以下になるようにしか道を通れない。
通行料をk以下にしつつ町Nまで行くための最短の移動距離を求めよ。
解法
酷い問題文ｗ
問題文に明記されていないのだが、道は全て一方通行である。
それでWA出した……orz
それに気をつければ、後は各都市のノードをその年についた時点でもってるコインの枚数で多重化してやることでダイクストラ法が適用可能な問題になる。
ソースコード
int k,n,r; vector<vector<pair<int,pi> > > e; bool V[10001][100]; int main() { scanf("%d%d%d",&k,&n,&r); e.resize(n); rep(i,r) { int s,d,l,t; scanf("%d%d%d%d",&s,&d,&l,&t); s--,d--; e[s].pb(mp(d,mp(l,t))); //e[d].pb(mp(s,mp(l,t))); } priority_queue<pair<int,pi> > Q; Q.push(mp(0,mp(0,k))); int ans=-1; while(!Q.empty()) { int cur=Q.top().second.first,coin=Q.top().second.second; int cc=Q.top().first; Q.pop(); if(V[coin][cur])continue; V[coin][cur]=1; if(cur==n-1) { ans=-cc; break; } fr(i,e[cur]) { if(i->second.second>coin)continue; int ncoin=coin-i->second.second; if(V[ncoin][i->first])continue; Q.push(mp(cc-i->second.first,mp(i->first,ncoin))); } } cout<<ans<<endl; return 0; }
3435 Sudoku Checker
問題概要
N^2*N^2のサイズの数独の初期配置が与えられる。矛盾しているかどうかを調べよ。
解法
パズルを解く必要はない。初期配置で縦、横、同じ区切りに同じ数字がないかどうかだけを見るという問題。
ソースコード
int n; int num[100][100]; bool ck() { rep(i,n*n) { bool use[101]={0}; rep(j,n*n)if(num[i][j]) { if(use[num[i][j]])return 0; use[num[i][j]]=1; } } rep(j,n*n) { bool use[101]={0}; rep(i,n*n)if(num[i][j]) { if(use[num[i][j]])return 0; use[num[i][j]]=1; } } rep(i,n)rep(j,n) { bool use[101]={0}; rep(dy,n)rep(dx,n)if(num[n*i+dy][n*j+dx]) { if(use[num[n*i+dy][n*j+dx]])return 0; use[num[n*i+dy][n*j+dx]]=1; } } return 1; } int main() { scanf("%d",&n); rep(i,n*n)rep(j,n*n)scanf("%d",num[i]+j); cout<<(ck()?"":"IN")<<"CORRECT"<<endl; return 0; }
1088 滑雪
解法
山の高さは場所ごとに一意であるため、地点を決めるとそこから移動できる距離も一意にきまる。したがって一度探索したらメモ化しておいて、二回目以降そのマスを探索するときはメモを渡すようにする。
ソースコード
int h,w,hi[100][100]; int memo[100][100]; #define ck(a,b) (0<=a&&a<b) int dy[]={-1,0,1,0},dx[]={0,-1,0,1}; int rec(int y,int x) { if(memo[y][x])return memo[y][x]; int ret=0; rep(d,4) { int ny=y+dy[d],nx=x+dx[d]; if(!ck(ny,h)||!ck(nx,w)||hi[ny][nx]>=hi[y][x])continue; ret=max(ret,rec(ny,nx)); } return memo[y][x]=ret+1; } int main() { scanf("%d%d",&h,&w); rep(i,h)rep(j,w)scanf("%d",hi[i]+j); int ans=0; rep(i,h)rep(j,w) { ans=max(ans,rec(i,j)); NEXT:; } cout<<ans<<endl; return 0; }
1323 Game Prediction
問題概要
1からN*Mまでの数字の書かれたN*M枚のカードがあり、それをM人のプレイヤーにN枚ずつ配る。
それぞれのプレイヤーが同時に一枚ずつカードを出し、最も高いカードを出したプレイヤーがそのラウンドの勝者となるようなゲームをN回行う。
このとき与えられた手札で勝つことのできる最低数を最大にするような手札の出し方について、その勝利数を求めよ。
解法
最悪のケースを想定するため、（敵が自分に合わせて手札を出してくると考えてよい）
手札を強い順に出すとしても一般性を失わない。
場の最も高いカードを自分が持っていればそのラウンドで勝てる。
今までのラウンドで使ったカードを覚えて、Nラウンドシミューレートする。
ソースコード
int main() { int m,n,cs=1; while(cin>>m>>n,m) { bool use[m*n]; fill(use,use+m*n,0); int cd[n]; rep(i,n)cin>>cd[i],cd[i]--; sort(cd,cd+n,greater<int>()); int ans=0,best=m*n-1; rep(i,n) { if(best==cd[i])ans++; else use[cd[i]]=1; use[best]=1; while(use[best])best--; } cout<<"Case "<<cs++<<": "<<ans<<endl; } return 0; }
2664 Prerequisites?
問題概要
4桁の講義番号で表される講義をk個受講する。
卒業までにはm個のカテゴリの講義についてそれぞれc個のうちr個以上を受講しなければならない。受講する講義は卒業の条件を満たしているか判定せよ。
解法
シミュレート。ただしジャッジデータの量が多いらしいので、講義番号をstringのsetで……みたいなことをするとTLE（になったorz）
番号は4桁なので1万までの配列で記録すればよい。
ソースコード
bool sel[10000]; int main() { int k,m; while(cin>>k>>m,k) { fill(sel,sel+10000,0); bool owata=0; rep(i,k) { int t; cin>>t; sel[t]=1; } rep(i,m) { int r,c,cnt=0; cin>>c>>r; rep(j,c) { int t; cin>>t; if(sel[t])cnt++; } if(cnt<r)owata=1; } cout<<(owata?"no":"yes")<<endl; } return 0; }
2818 Making Change
問題概要
レジにはそれぞれa枚,b枚,c枚,d枚の25セント,10セント,5セント,1セント硬貨がある。
与えられた金額(0-99セント)を最小枚数で支払うような支払い方を求めよ。
解法
金額の値が小さいので動的計画法などの工夫はしなくともよい。
ソースコード
int n[4],coin[4]={25,10,5,1},cent; int use[4],ans[4],mn; bool ok; void rec(int cur,int r,int c) { if(cur==4) { if(r!=0||c>=mn)return; rep(i,4)ans[i]=use[i]; ok=1; mn=c; return; } rep(i,n[cur]+1) { if(r>=i*coin[cur]) { use[cur]=i; rec(cur+1,r-i*coin[cur],c+i); } } } int main() { int a,b,c,d; while(cin>>a>>b>>c>>d>>cent,a||b||c||d||cent) { n[0]=a,n[1]=b,n[2]=c,n[3]=d; ok=0; mn=inf; rep(i,4)use[i]=0; rec(0,cent,0); if(ok)cout<<"Dispense "<<ans[0]<<" quarters, "<<ans[1]<< " dimes, "<<ans[2]<<" nickels, and "<<ans[3]<<" pennies."<<endl; else cout<<"Cannot dispense the desired amount."<<endl; } return 0; }
1326 Mileage Bank
問題概要
飛行機に乗ると以下のようにマイルがたまる。
- エコノミークラス
- 実際の飛行距離が500未満：500
500以上：その距離 - ビジネスクラス
- 実際の飛行距離+実際の飛行距離の50%分ボーナス
- ファーストクラス
- 実際の飛行距離+実際の飛行距離の100%分ボーナス
（端数は全て切り上げ）
利用記録が与えられた時たまるマイルの量を求めよ。
解法
シミュレート。
ソースコード
int main() { string str,cls; while(getline(cin,str),str!="#") { int ans=0; do { stringstream ss(str); int ac; ss>>cls>>cls>>ac>>cls; if(cls=="Y")ans+=max(500,ac); else if(cls=="B")ans+=ac+(ac+1)/2; else ans+=ac*2; }while(getline(cin,str),str!="0"); cout<<ans<<endl; } return 0; }
