PKU演習問メモ(4/5)
フォーマットを変えてみるテスト。こちらのほうが見やすいでしょうか？＞閲覧者様（果たして定期的にこの日記読んで下さってる方はいらっしゃるのか……？）
| No. | Title | 分類・解法 |
|---|---|---|
| 3300 | Tour de France | Straight forward |
| 3364 | Black and white painting | Simple Math |
| 3366 | Deli Deli | String manipulation |
| 3444 | Wavelet Compression | Straight forward |
| 3427 | Ecology tax | Simple Math |
| 3445 | Elementary Additions | String manipulation |
| 3507 | Judging Olympia | Straight forward |
| 3522 | Slim Span | Graph, Prim's algorithm |
| 3618 | Exploration | Straight forward |
| 3624 | Charm Bracelet | Knapsack problem, Dynamic programming |
| 3672 | Long Distance Racing | Straight forward |
ついでにデザインも変更してみた。
問題要約・解説など↓
3300 Tour de France
問題概要
自転車のギアの前の歯数（複数から切り替え）と後ろの歯数（こちらも）が与えられる。このとき「運転比」を前の歯数/後ろの歯数で定める。運転比を小さい順に並べた時、隣り合う値の比の最大値を求めよ。
解法
set
3364 Black and white painting
問題概要
nxmマスの市松模様の板がある。n,mの値と右下のマスの色が与えられた時、8x8のチェスボード（右下のマスは白）が何通り含まれるかを求めよ。
解法
市松板の右下のマスが白か黒かで場合分け。更にチェスボードの右下のマスが偶数列にくるか奇数列に来るかで場合分け。それで数え上げればよい。
3366 Deli Deli
問題概要
以下の規則にしたがって単語の複数形を答えよ。
- 例外規則が与えられている場合それを出力
- それ以外で、単語が子音字+yで終わる場合yをiesに置換
- それ以外で、単語がo,s,ch,sh,xで終わる場合esを付加
- それ以外の場合sを付加
問題文に与えられた順序の通りに処理していく。
3444 Wavelet Compression
問題概要
ウェーブレット変換（さざなみ変換？）の簡易版を考える。
項数が2^kの自然数列について以下の変換をほどこすものとする。
数列の隣り合う項を二つずつ取っていく。
項をa[2*i],a[2*i+1]とするとその和をs(i)、その差をd(i)として
s(i)=a[2*i]+a[2*i+1],d(i)=a[2*i]-a[2*i+1]と書ける。
新しい数列a[n]はs(i)をi=1...n/2まで並べた後にd(i)をi=1...n/2まで並べたものである。
次に、新しい数列の前半についてn=n/2として同じ操作を施す。
n=1になるまで繰り返し操作を施した後のa[n]を変換されたa[n]という。
a[n]の変換後の数列が与えられた時、変換前の数列を求めよ。
解法
定義にしたがってn=2からどんどん逆変換していけばいい。
3427 Ecology tax
問題概要
1年に1メートルずつ伸びる木がn本あり、現在の長さはl[i]である。
ある企業がこの木を一度に伐採したいが、長さL単位でしか伐採できず、端数は無駄になり税がかかる。無駄が最小になるように木が成長するのは最短で何年後かを求めよ。
解法
0〜L-1年後までだけを考えればよい。
今の木の長さがaであるような木の本数の配列をd[a]とすれば、
t年後に伐採するとしたときに出る端数はΣ[0≦a＜L]d[(a-t)%L]*a
これをループで全列挙すればおｋ.O(Ln).オーダー的にあやしい気がしたが通ってしまった……
ソースコード
int n,l,d[30001]; int main() { scanf("%d%d",&n,&l); rep(i,n) { int t; scanf("%d",&t); d[t%l]++; } int ans=-1,mn=inf; rep(i,l) { int tx=0; rep(j,l)tx+=d[(j+l-i)%l]*j; if(tx<mn)mn=tx,ans=i; } cout<<ans<<endl; return 0; }
3445 Elementary Additions
問題概要
非負整数を以下のように集合としてあらわす。
- 0={}
- n>0なる全てのnについてn={x|x
二つの数を表す集合が文字列の形で与えられる時、その和をあらわす集合を出力せよ。
解法
和は15以下であることが問題文より保証されているので、15まで最初に文字列を作っておく。
3507 Judging Olympia
問題概要
プログラミングコンテストの結果について6種類の評価点が与えられ、最終点をその最大値と最小値を除いたものの平均と定める。最終点を求めよ。
解法
足し算して引き算して割り算すればおｋ.
3522 Slim Span
問題概要
与えられたグラフの全域木のうち、最大辺と最小辺の差が最も小さいものをslim spanと呼ぶ。slim spanの最大辺と最小辺の差を求めよ。
グラフの用語がわからない人はwikipedia等を参考に。
解法
最小辺を決め付けて、それ以上の辺だけをPrim法でつなぐ。
時間制限ギリギリではあるが特に工夫もせず通った。
（辺の長さの入った配列をソートして、ある長さを最小値に決め付けて失敗したらそれ以上で全域木は作れないので即座に終了などの工夫が考えられる）
ソースコード
int n,m,w[100][100]; int allw[10000]; int main() { while(cin>>n>>m,n) { rep(i,n)fill(w[i],w[i]+n,inf); int cnt=0; rep(i,m) { int a,b,c; cin>>a>>b>>c; a--,b--; w[a][b]=w[b][a]=c; allw[cnt++]=c; } int ans=inf; //Prim for m times rep(iter,m) { int mx=0,vis=0; bool V[n]; fill(V,V+n,0); priority_queue<pi> Q; Q.push(mp(0,0)); while(!Q.empty()) { int cur=Q.top().second; int c=Q.top().first; Q.pop(); if(V[cur])continue; V[cur]=1; vis++; mx=max(mx,-c); if(vis==n) { ans=min(ans,mx-allw[iter]); break; } rep(i,n)if(w[cur][i]!=inf&&!V[i]) if(w[cur][i]>=allw[iter])Q.push(mp(-w[cur][i],i)); } } cout<<(ans==inf?-1:ans)<<endl; } return 0; }
3618 Exploration
問題概要
数直線上にN個の標識が並んでいる。
原点にいる人が総移動距離T以内で、原点に距離の近い標識から順に訪れていく。訪れることのできる標識の総数を求めよ。どの二つの標識も原点から同じ距離にはないとする。
解法
絶対値でソートしてグリーディーに訪れていく。
ソースコード
int t,n,x[50000]; bool cmp(int a,int b) { return abs(a)<abs(b); } int main() { scanf("%d%d",&t,&n); rep(i,n)scanf("%d",x+i); sort(x,x+n,cmp); int c=0,i=0; for(;i<n&&t>=abs(x[i]-c);i++) { t-=abs(x[i]-c); c=x[i]; } cout<<i<<endl; return 0; }
3624 Charm Bracelet
問題概要
ブレスレットに宝石をつける。各宝石の価値と重さが与えられた時、宝石の重さの合計をm以下にしつつ価値を最大にしたい。各宝石は一度以下しか用いることはできない。最大の価値を求めよ。
ソースコード
int n,m,w[3402],d[3402]; int dp[12881],mx,ans; int main() { cin>>n>>m; rep(i,n)cin>>w[i]>>d[i]; rep(i,n)for(int j=m;j>=w[i];j--) { dp[j]=max(dp[j],dp[j-w[i]]+d[i]); ans=max(ans,dp[j]); } cout<<ans<<endl; return 0; }
