PKU演習問メモ(8/16)
| No. | 問題名 | 問題の種類および解法 | 難易度 |
|---|---|---|---|
| 3279 | Fliptile | 探索（ライツアウト） | ★★☆☆☆ |
| 3256 | Cow Picnic | 深さ優先探索 | ★★☆☆☆ |
| 3432 | Count Squares | 二分探索 | ★★★☆☆ |
| 3665 | iCow | シミュレーション | ★☆☆☆☆ |
| 3724 | Find the parameter | 深さ優先探索・誤差 | ★★☆☆☆ |
3279 Fliptile
問題概要
mxnのライツアウトがある。
盤面をすべて0にするような解法で、手数が最小のものを、それが複数ある場合その中で辞書順で最小のものを求めよ。
解法が存在しない場合"IMPOSSIBLE"を出力せよ。
解法
定石どおり端の一列を2^m全て試す。後は一意に解法が定まる。
成功したら最短手数のものを覚える。
ソースコード
int dy[]={-1,0,1,0,0},dx[]={0,-1,0,1,0}; int h,w,cl[15][15]; int tmp[15][15],tmpa[15][15],tmpc; void flip(int y,int x) { tmpa[y][x]=1; tmpc++; rep(d,5) { int ny=y+dy[d],nx=x+dx[d]; if(ny<0||ny>=h||nx<0||nx>=w)continue; tmp[ny][nx]^=1; } } bool cmp(int a[15][15],int b[15][15]) { rep(i,h)rep(j,w)if(a[i][j]!=b[i][j])return a[i][j]>b[i][j]; return 0; } int main() { scanf("%d%d",&h,&w); rep(i,h)rep(j,w)scanf("%d",cl[i]+j); int cnt=inf,ans[15][15]; rep(bit,1<<w) { tmpc=0; rep(i,h)rep(j,w)tmp[i][j]=cl[i][j],tmpa[i][j]=0; rep(i,w)if(bit&1<<i)flip(h-1,i); for(int i=h-2;i>=0;i--)rep(j,w) if(tmp[i+1][j])flip(i,j); rep(i,w)if(tmp[0][i])goto NEXT; if(tmpc<cnt||tmpc==cnt&&cmp(ans,tmpa)) { cnt=tmpc; rep(i,h)rep(j,w)ans[i][j]=tmpa[i][j]; } NEXT:; } if(cnt==inf)puts("IMPOSSIBLE"); else rep(i,h)rep(j,w)printf("%d%c",ans[i][j],j==w-1?'\n':' '); return 0; }
3256 Cow Picnic
問題概要
k頭の牛が居る牧草地の番号がそれぞれ与えられる。
牧草地は全部でn個あり、それぞれはm本の一方通行の道で結ばれている。
これらの道が与えられたとき、全ての牛が到達可能な牧草地の数を求めよ。
k≦100,
n≦1000,
m≦10000を満たす。
解法
それぞれの牛の場所からDFSして、到達可能か見る。
最後に、全てから到達可能な点を数えて出力する解法で間に合う。
計算量はO((m+n)k).
ソースコード
int k,n,m,in[100]; vector<vi> e; bool V[1001]; int cnt[1001]; void dfs(int c) { V[c]=1; fr(i,e[c])if(!V[*i])dfs(*i); } int main() { scanf("%d%d%d",&k,&n,&m); e.resize(n); rep(i,k)scanf("%d",in+i),in[i]--; rep(i,m) { int a,b; scanf("%d%d",&a,&b); e[a-1].pb(b-1); } rep(i,k) { rep(j,n)V[j]=0; dfs(in[i]); rep(j,n)cnt[j]+=V[j]; } int ans=0; rep(i,n)if(cnt[i]==k)ans++; printf("%d\n",ans); return 0; }
3432 Count Squares
問題概要
平面上にn個の点がある。
それらを4頂点とするような正方形の個数を求めよ。
n≦2000かつ、与えられる座標の全ての値は絶対値が10000以下の整数である。
解法
PKU 2002と全く同じ問題。
2点を適当に取ると、残りの2点の座標は定まるので、二分探索すればよい。
ソースコード
int n; pi p[2000]; int main() { scanf("%d",&n); rep(i,n)scanf("%d%d",&p[i].first,&p[i].second); sort(p,p+n); int cnt=0; rep(i,n)rep(j,i) { int dx=p[i].first-p[j].first,dy=p[i].second-p[j].second; if(binary_search(p,p+n,mp(p[i].first-dy,p[i].second+dx))&& binary_search(p,p+n,mp(p[j].first-dy,p[j].second+dx))) cnt++; } printf("%d\n",cnt/2); return 0; }
3665 iCow
問題概要
音楽プレイヤーiCowは以下のアルゴリズムに従い曲のシャッフル順を決定する。
- 全ての曲は初期レーティングR[i]がつけられている
- 次に演奏される曲はレーティングが最大のものである（同じものがある場合その中で番号が最小のもの）
- 曲が演奏された後、その曲のレートは0になり、その曲のレートは残りの曲に分配される
- 上において等分ができないときは最初のほうから配られる曲に1ずつ多く分配される
このときシャッフル順で演奏される最初のT曲の番号を出力せよ。
曲数N≦1000,
T≦1000,
R[i]≦10000を満たす。
ソースコード
int n,t,r[1000]; int main() { scanf("%d%d",&n,&t); rep(i,n)scanf("%d%",r+i); if(n==1) { rep(i,t)puts("1"); return 0; } rep(i,t) { int p=max_element(r,r+n)-r; printf("%d\n",p+1); int one=r[p]/(n-1),re=r[p]%(n-1); rep(j,n)if(j!=p) { r[j]+=one; if(re>0)r[j]++,re--; } r[p]=0; } return 0; }
3724 Find the parameter
問題概要
関数
y=exp(a0x0)+exp(a1x1)+……+exp(a9x9)
が通る点N個の座標が与えられる。
aiは1以上9以下の整数であり、全てのiに対してai≦ai+1を満たす。
このときa0〜a9の値を求めよ。
与えられる点のx座標は0以上5以下、N≦20としてよい。
解法
深さ優先探索で全通り試す。
残りを全て最小にしてもyを超える場合、あるいは残り全てを最大にしてもyに届かない場合を刈るような枝刈りを入れたが、なくても通る。
disscussで言われているように、誤差の扱いがおかしい模様。
EPS=1にして、最後の答えの判定を(int)(a*1000+0.5!=)にしたら通った。
long doubleもなしで通るみたい。ちょっと悪問？
ソースコード
typedef long double ld; const ld EPS=1; int n; ld X[20],Y[20]; ld sum[20],lo[20][11],hi[20][11]; int a[10]; bool ck(int c) { if(c==10) { rep(i,n)if((int)(sum[i]*1000+0.5)!=(int)(Y[i]*1000+0.5))return 0; return 1; } rep(i,n) { if(Y[i]>sum[i]+hi[i][c]+EPS)return 0; if(Y[i]<sum[i]+lo[i][c]-EPS)return 0; } return 1; } bool dfs(int c,int p) { if(c==10)return 1; for(int i=p;i<=10;i++) { a[c]=i; rep(j,n)sum[j]+=exp(X[j]*i); if(ck(c+1)&&dfs(c+1,i))return 1; rep(j,n)sum[j]-=exp(X[j]*i); } return 0; } int main() { cin>>n; rep(i,n)cin>>X[i]>>Y[i]; rep(i,n) { lo[i][10]=hi[i][10]=0; for(int j=9;j>=0;j--) { lo[i][j]=lo[i][j+1]+exp(X[i]); hi[i][j]=hi[i][j+1]+exp(X[i]*10); } sum[i]=0; } dfs(0,1); rep(i,10)cout<<a[i]<<endl; return 0; }
