PKU演習問メモ(9/2)
解説まとめるのめんどい……あとであとで←かいたー！
| No. | 問題名 | 問題の種類および解法 | 難易度 |
|---|---|---|---|
| 1860 | Currency Exchange | ベルマン・フォード | ★★★☆☆ |
| 1861 | Network | クラスカル法 | ★★☆☆☆ |
| 2356 | Find a multiple | 動的計画法or鳩ノ巣原理 | ★★★★☆ |
| 2631 | Roads in the North | グラフ・動的計画法 | ★★★☆☆ |
| 2694 | A Simple Poker Game | 実装 | ★★☆☆☆ |
| 2659 | Bomb Game | 実装 | ★★☆☆☆ |
| 2607 | Fire Station | ワーシャルフロイド | ★★☆☆☆ |
| 2641 | Billiard | 幾何 | ★☆☆☆☆ |
| 2675 | Songs | 貪欲法 | ★★★☆☆ |
1860 Currency Exchange
問題概要
n個の為替交換所がある。
それぞれA[i]とB[i]の通貨をA[i]→B[i]をレートrab[i],手数料cab[i],B[i]→A[i]をレートrba[i],手数料cba[i]で交換してくれる。
今元手にSの通貨をVの量だけもっている。
このとき、これらの交換所を利用して、元手を増やすことができるかを判定せよ。
A→Bに通貨を変えるとき持っているAの量をAとすれば買うことのできるBの量は、
(A-cab)*rabに等しい。
解法
ベルマンフォードのアルゴリズムにより負回路を検出すればよい。
ベルマンフォードを使ったのは初めてなので一応メモ。
O(EV)で最短路を求める動的計画法の一種で、同時に負回路の検出ができる。
k回、それぞれの辺について辿れる最短距離の表を更新するループをまわすと、
k回の移動で行けるノードへの最短距離が求まる。
それをn-1回行えば、全部のノードへの最短距離がわかる。
n回行った時点で、更に距離が更新されれば、それは負回路があることになる。
ソースコード
int n,m,s; double v; vector<vector<pair<int,pair<double,double> > > >e; double cap[100]; bool ck() { rep(i,n)cap[i]=0; cap[s]=v; rep(k,n)rep(i,n)fr(j,e[i]) { double nc=(cap[i]-j->second.second)*j->second.first; if(cap[j->first]<nc) { cap[j->first]=nc; if(k==n-1)return 1; } } return 0; } int main() { scanf("%d%d%d%lf",&n,&m,&s,&v); s--; e.resize(n); rep(i,m) { int a,b; double rab,cab,rba,cba; scanf("%d%d%lf%lf%lf%lf",&a,&b,&rab,&cab,&rba,&cba); a--; b--; e[a].pb(mp(b,mp(rab,cab))); e[b].pb(mp(a,mp(rba,cba))); } puts(ck()?"YES":"NO"); return 0; }
1861 Network
問題概要
いくつかのハブをいくつかの双方向に通信可能なケーブルが結んでいる。
任意のハブから任意のハブへの経路は存在し、かつ一意に定まる。
このとき、"最大のケーブルの長さ"を最小にするような全域木を出力せよ。
入力のケーブルの本数は10000本以内である。
ソースコード
int n,m; vector<pair<int,pi> >e; int p[1001]; int root(int x) { if(x==p[x])return x; return p[x]=root(p[x]); } int main() { scanf("%d%d",&n,&m); rep(i,m) { int a,b,c; scanf("%d%d%d",&a,&b,&c); e.pb(mp(c,mp(a,b))); } sort(all(e)); rep(i,n+1)p[i]=i; int a1[1000],a2[1000],l=0,mx; rep(i,m) { int a=e[i].second.first,b=e[i].second.second; a=root(a); b=root(b); if(a==b)continue; a1[l]=e[i].second.first; a2[l]=e[i].second.second; p[b]=a; l++; if(l==n-1) { mx=e[i].first; break; } } printf("%d\n%d\n",mx,l); rep(i,l)printf("%d %d\n",a1[i],a2[i]); return 0; }
2356 Find a multiple
問題概要
15000以下の数がN個与えられる。
N個の数のうち1つ以上N個以下を選び、それらの和がN*k（kは自然数）になるようにしたい。
そのような数を出力せよ。答えが複数ある場合どれを出力してもかまわない。
N≦10000を満たす。
解法
鳩ノ巣のO(n)解法があるっぽい。
v[i]に(Σa[i])%nが出現したかどうか入れておく。
v[i]がぶつかったら、v[j]-v[i]≡0になるので、iからj間の数を出力すればよい。
配列は0〜n-1のn個で、a[i]もn個なので必ずどこかで衝突がおこる。
DP解法は普通にやるとTLEで、変な枝刈りいれたりしたら通ったのであんまり想定解ではない気がする。
dp[i][j]にi個の数字を使って和j(mod n)が作れるかをもっておき、表を更新しておく。
経路の出力用にp[i]に、その和へ来るのに使った数字を持っておく。
n*kが作れることが確定したらすぐにループを抜ける。
ソースコード
DP解法
int n,in[10000],a[10000]; int d[10000],p[10000]; bool dp[2][10000]; int main() { scanf("%d",&n); int s=0; rep(i,n)scanf("%d",in+i),a[i]=in[i]%n,s+=a[i]; if(s%n==0) { printf("%d\n",n); rep(i,n)printf("%d\n",in[i]); return 0; } int cur=0,next=1; rep(i,n) { rep(j,n)dp[next][j]=dp[cur][j]; if(!dp[next][a[i]]) { dp[next][a[i]]=1,d[a[i]]=a[i],p[a[i]]=in[i]; if(a[i]==0)break; } rep(j,n)if(dp[cur][j]) { int nj=j+a[i]; if(nj>=n)nj-=n; if(dp[next][nj])continue; dp[next][nj]=1; d[nj]=a[i]; p[nj]=in[i]; if(nj==0)break; } cur^=1; next^=1; } int ans[10000],na=0; cur=0; do { ans[na++]=p[cur]; cur-=d[cur]; if(cur<0)cur+=n; }while(cur); printf("%d\n",na); while(na--)printf("%d\n",ans[na]); return 0; }
2631 Roads in the North
問題概要
木が与えられる。
それらの二つのノードのうち、距離が最も離れたノード間の距離を求めよ。
ノードの数は10000以下である。
解法
典型的なツリーDP.
自分以下で最も遠い子への距離をfar[i]に入れて更新していく。
答えは、遠い子1+遠い子2または自分の子の中での遠いノード間。
ソースコード
vector<vector<pi> > e; int in[10000][3]; int ans,far[10000]; void dfs(int c,int p) { int a=0,b=0,t; fr(i,e[c])if(i->first!=p) { dfs(i->first,c); t=far[i->first]+i->second; far[c]=max(far[c],t); if(a<t)b=a,a=t; else if(b<t)b=t; } ans=max(ans,a+b); } int main() { int n=0; while(~scanf("%d%d%d",in[n],in[n]+1,in[n]+2))n++; e.resize(n+1); rep(i,n) { e[in[i][0]-1].pb(mp(in[i][1]-1,in[i][2])); e[in[i][1]-1].pb(mp(in[i][0]-1,in[i][2])); } dfs(0,0); printf("%d\n",ans); return 0; }
2694 A Simple Poker Game
問題概要
52枚のデッキから引かれた5枚のカードが与えられる（順序はバラバラ）。
この手札の点数を出力せよ。役は以下の通りである。
- ストレートフラッシュ(1000)
- 5枚のカードのスーツが同じで、ランクが連続している。XJQKAは連続した数とみなされる。
- フォーオブアカインド(750)
- 4枚のカードのランクが同じ。
- フルハウス(500)
- 手札がランクが同じ3枚のカードとランクが同じ2枚のカードからなる。
- フラッシュ(350)
- 5枚のカードのスーツが同じ。
- ストレート(250)
- 5枚のカードのランクが連続している。XJQKAは連続した数とみなされる。
- スリーオブアカインド(200)
- 3枚のカードのランクが同じ。
- ツーペア(100)
- ランクの同じ2枚のカードおよび別のランクの同じ2枚のカードがある。
- ワンペア(50)
- 2枚のカードのランクが同じ。
- それ以外(0)
- それ以外。
役は最も点数の高いもの一つのみが適用されるものとする。
解法
役を点数の高い順に判定していく。
ストレートはA2345とXJQKAはありえるが、QKA23などはありえないことに注意。
（実際のポーカーでもそう）
ソースコード
int ck(bool h[4][13]) { bool straight=0,flush=0; rep(i,10) { bool ok=1; rep(j,5) { bool f=0; rep(k,4)if(h[k][(i+j)%13]) { f=1; break; } if(!f) { ok=0; break; } } if(ok) { straight=1; break; } } rep(i,4) { int cnt=0; rep(j,13)if(h[i][j])cnt++; if(cnt==5)flush=1; } if(straight&&flush)return 1000; int four=0,three=0,two=0; rep(i,13) { int cnt=0; rep(j,4)if(h[j][i])cnt++; if(cnt==2)two++; else if(cnt==3)three++; else if(cnt==4)four++; } if(four)return 750; if(three&&two)return 500; if(flush)return 350; if(straight)return 250; if(three)return 200; if(two==2)return 100; if(two)return 50; return 0; } int main() { char S[256],R[256]; S['C']=0; S['D']=1; S['H']=2; S['S']=3; for(int i=2;i<=9;i++)R['0'+i]=i-1; R['A']=0; R['X']=9; R['J']=10; R['Q']=11; R['K']=12; int cs; scanf("%d",&cs); while(cs--) { bool h[4][13]={0}; char s,r; rep(i,5)scanf(" %c %c",&s,&r),h[S[s]][R[r]]=1; printf("%d\n",ck(h)); } return 0; }
2659 Bomb Game
問題概要
A行B列のグリッドからなるフィールドに、Suskoが好きな場所に箱を置き、Boskoが爆弾を置いて爆破し、爆弾の座標および爆風の大きさ・箱が巻き込まれたかどうかの結果が与えられる。
この試行を何回か繰り返した結果が与えられるとき、（箱の場所は途中で変わらない）
箱の場所の候補地としてありえるものの数を求めよ。
A≦100,B≦100であり、
爆風は座標(R,S)を中心とする、大きさP（Pは奇数）の正方形とする。
解法
初めは全てのグリッドを候補地としておく。
箱がまきこまれた場合正方形の外部が候補地としてありえなくなり、
箱がまきこまれなかった場合、正方形の内部が候補地としてありえなくなる。
最後に残っているグリッドの数を数えればよい。
ソースコード
int w,h,k; bool cand[100][100]; int main() { scanf("%d%d%d",&h,&w,&k); rep(i,h)rep(j,w)cand[i][j]=1; rep(i,k) { int r,s,p,t; scanf("%d%d%d%d",&r,&s,&p,&t); r--; s--; p/=2; rep(y,h)rep(x,w) if(t^(abs(r-y)<=p&&abs(s-x)<=p))cand[y][x]=0; } int ans=0; rep(i,h)rep(j,w)if(cand[i][j])ans++; printf("%d\n",ans); return 0; }
2607 Fire Station
問題概要
n個の交差点が何本かの道路によってつながれている。
道路はそれぞれ始点a[i],終点b[i],長さd[i]によって与えられ、双方向に通行可能である。
交差点のうち与えられたf個には消防署がある。
更に一つ消防署を、「最寄の消防署との距離が最も遠い交差点と、消防署との距離」が最小になるように追加したい。
そのような消防署の場所を求めよ。
f≦100,n≦500を満たす。
解法
まず各交差点間の最短距離をワーシャルフロイド法によって求める。
そして、新たに設置する消防署を全通り試す。
元々の最寄の消防署との距離はあらかじめ計算しておくことで、計算量を減らすことができる。
ソースコード
int nf,ni,pf[100]; int d[500][500],near[500]; int main() { scanf("%d%d",&nf,&ni); rep(i,nf)scanf("%d",pf+i),pf[i]--; rep(i,ni)rep(j,ni)d[i][j]=i!=j?inf:0; int a,b,c; while(~scanf("%d%d%d",&a,&b,&c)) { a--; b--; d[a][b]=d[b][a]=c; } rep(k,ni)rep(i,ni)rep(j,ni)d[i][j]=min(d[i][j],d[i][k]+d[k][j]); rep(i,ni)near[i]=inf; rep(i,ni)rep(j,nf)near[i]=min(near[i],d[i][pf[j]]); int mn=inf,mi=0; rep(i,ni) { int mx=0; rep(j,ni)mx=max(mx,min(near[j],d[j][i])); if(mx<mn)mn=mx,mi=i; } printf("%d\n",mi+1); return 0; }
2641 Billiard
問題概要
幅A奥行きBのビリヤード台の中央から球を発射すると、横の壁にm回、横の壁にn回ぶつかって、s秒後に元の場所へ返ってきた。
このとき、球を打ち出した角度および球の速度を求めよ。
ビリヤードの球は台と完全弾性衝突し、大きさは無視できるものとする。
解法
反射する=鏡像を作るのが定石。
球は台の中央にあるので対称の位置を考える必要はない。
ソースコード
int w,h,s,m,n; int main() { while(scanf("%d%d%d%d%d",&w,&h,&s,&m,&n),w) { h*=n; w*=m; double a=atan2(h,w),v=hypot(h,w)/s; printf("%.2f %.2f\n",a*180/PI,v); } return 0; }
2675 Songs
問題概要
n曲の曲についてその長さl[i]および再生頻度f[i]が与えられる。
これらの曲をテープに並べるのに、以下の量で表される再生時間の合計を最小にしたい。
Σ[i=1,n]f[s[i]]Σ[j=1,s[i]]l[s[j]]
このとき、テープにs番目にくる曲の番号を求めよ。
n≦65535を満たす。
解法
問題文間違ってないかこれ。
Σ[i=1,n]f[s[i]]Σ[j=1,i]l[s[j]]
じゃないのか？？
よくわからないけどl/fの順に並べてみたらそれっぽかった。
複数ケースに対応させないとWA.
l/fはすぐ思い浮かんだけど証明ができない。
ソースコード
int n,s; pair<double,int> song[100000]; int main() { while(~scanf("%d",&n)) { rep(i,n) { int a,l; double f; scanf("%d%d%lf",&a,&l,&f); song[i]=mp(l/f,a); } scanf("%d",&s); sort(song,song+n); printf("%d\n",song[s-1].second); } return 0; }
