PKU演習問メモ（4/12）
- 今日中に400問は無理そうだorz自分がへぼすぎて鬱……
- 昨日のCodeforcesのE問題、書いてみたのだけどWAる（case 28）……
他の人のコードを見るに方針はあってるっぽいのだけど。
| No. | Title | 分類・解法 | 主観的難易度 |
|---|---|---|---|
| 2051 | Args | 実装問題 | ★★☆☆☆ |
| 2005 | Blackjack | 実装問題 | ★☆☆☆☆ |
| 2721 | Suit Distribution | 実装問題、数学 | ★☆☆☆☆ |
| 3264 | Balanced Lineup | Range minimum query | ★★★☆☆ |
| 2155 | Matrix | ビット演算 | ★★★☆☆ |
分類・解法は日本語にすることにした。
多分そのほうが検索する人がやりやすいと思うので……
以下問題概要や解説など↓
2051 Argus
問題概要
ID番号と時間の間隔のリストが与えられる。それぞれのqueueがそれぞれの間隔ごとに実行されるとき、実行されるのが早い順からK個のqueueのID番号を求めよ。
解法
k個の配列に「現在の早い順にk個」を記録しておき、それぞれのID毎にk個の記録を更新していく。
k個の配列はソート済みであるので二分探索が使える（STLのlower_bound）のと、あらかじめ間隔の短い順にリストをソートしておけることで記録の更新回数を減らす工夫ができる。（TLEが少ないことを見るとやらなくても通りそうな気はするけれど）
工夫しなくても通るなら主観的難易度は1で。
ソースコード
int n,k; pi reg[3000],ans[10000]; int main() { char str[99]; while(scanf("%s",str),strcmp(str,"#")) { int a,b; scanf("%d%d",&a,&b); reg[n].first=b,reg[n].second=a; n++; } sort(reg,reg+n); scanf("%d",&k); rep(i,k)ans[i]=mp(reg[0].first*(i+1),reg[0].second); for(int i=1;i<n;i++) { pi tmp=mp(reg[i].first,reg[i].second); for(int j=1;j<k;j++) { if(tmp>ans[k-1])break; int p=lower_bound(ans,ans+k,tmp)-ans; rotate(ans+p,ans+(k-1),ans+k); ans[p]=tmp; tmp.first+=reg[i].first; } } rep(i,k)printf("%d\n",ans[i].second); return 0; }
2005 Blackjack
問題概要
n組のトランプを使うディーラーと子の一対一のブラックジャックにおいて、
ディーラーの1枚目の手札、子の2枚の手札が与えられたとき、子の勝つ確率を求めよ。
点数と勝敗の決定のしかたは以下の通りである。
子の勝利条件
- 子の手札の点数が21を超えない
- かつ、子の点数が親の手札の点数を超えているまたは親の手札の点数が21を超えている。
点数
- A 1点または11点（11点にしても点数が21を超えなかったら11点）
- 2から10 数字どおりの点数
- 絵札 10点
解法
残りの山札のカード枚数と、ディーラーが引いたら子が勝つカードの枚数から確率を求めればよい。
ソースコード
int cd[256],pt[13]; int main() { cd['A']=0,cd['T']=9,cd['J']=10,cd['Q']=11,cd['K']=12; for(int i=2;i<10;i++)cd['0'+i]=i-1; rep(i,8)pt[i+1]=i+2; pt[9]=pt[10]=pt[11]=pt[12]=10,pt[0]=1; int n; while(cin>>n,n) { int ncd[13]; rep(i,13)ncd[i]=n*4; char a,b,c; cin>>a>>b>>c; ncd[cd[a]]--,ncd[cd[b]]--,ncd[cd[c]]--; int d=pt[cd[a]],p=pt[cd[b]]+pt[cd[c]]; if(a=='A'&&d<12)d+=10; if(b=='A'&&p<12)p+=10; if(c=='A'&&p<12)p+=10; double total=0,win=0; rep(i,13) { int tmpd=d+pt[i]; if(i==0&&tmpd<12)tmpd+=10; if(p<=21&&(p>tmpd||tmpd>21))win+=ncd[i]; total+=ncd[i]; } printf("%.3f%%\n\n",win/total*100); } return 0; }
2721 Suit Distribution
問題概要
ブリッジ（トランプのゲーム）において、オポーネント（対戦相手）のスペードの枚数がa+b枚であると解っているとする。
スペードがオポーネントにa枚、b枚でスプリットしている確率を求めよ。
要するに相手二人のそれぞれの13枚の手札にa枚、b枚スペードが入っている確率。
解法
中学校でやる確率の計算。a+b枚の分け方はc(a+b,26)通りで、aの分け方がc(a,13), bも同様。aとbが異なる場合は2!倍する。
splitをsplintなどとtypoしてWAを貰わないようにorz
ソースコード
double c(int n,int k) { double ret=1; rep(i,k)ret*=n-i,ret/=i+1; return ret; } int main() { int a,b; while(cin>>a>>b,~a) { double ans=(a==b?1:2)*c(13,a)*c(13,b)/c(26,a+b); printf("%d-%d split: %.8f\n",a,b,ans); } return 0; }
3264 Balanced Lineup
問題概要
数列a[i]の、p以上q以下の項の最大値-最小値を求めよ。
ただしa[i]の要素数は50000以下、求める差の個数は20万個以下である。
解法
Range minimum queryという有名問題。（らしい
右のリンクにもあるspaghetthi source様のコードをそのまま使ったorz
必ず後で自分で書けるようにするおorzorzorz
これってsegment木を使っても時間間に合うんだろうか。誰か教（ｒｙ
ソースコード
int h[50000],hm[50000]; int main() { int n,q; scanf("%d%d",&n,&q); rep(i,n) { int a; scanf("%d",&a); h[i]=a,hm[i]=-a; } int *mxq=buildRMQ(hm,n),*mnq=buildRMQ(h,n); rep(i,q) { int a,b; scanf("%d%d",&a,&b); a--,b--; printf("%d\n",-minimum(a,b,mxq,n)-minimum(a,b,mnq,n)); } return 0; }
ライブラリ部分は略。
2155 Matrix
問題概要
各成分が0または1のnxn行列Aについて次の操作をせよ。
- 左上が(x1,y1)、右下が(x2,y2)の長方形の領域の要素について、0と1を入れ替える
- Aのy行j列成分を出力する
解法
nが1000と大きいので工夫しないとTLEになる。
Aの各成分は0まはた1なので、ビット表現でまとめていくつかの成分を一つの変数にすることが思い浮かぶ。それを実装すればいい
あまりビット演算のコードを書いたことがないので（ビットDPくらい？）かなりややこしかったｗ
負数の場合ビットシフトと除算の結果が変わるということに気づかずはまった。
ソースコード
int n,t,w; ll a[1000][16]; int main() { int cs; scanf("%d",&cs); while(cs--) { scanf("%d%d",&n,&t); w=n/64+((n&63)!=0); rep(i,n)rep(j,w)a[i][j]=0; rep(T,t) { int x,y,x2,y2; char c; scanf(" %c",&c); if(c=='C') { scanf("%d%d%d%d",&x,&y,&x2,&y2); x--,y--; for(int i=y;i<y2;i++) { for(int j=x/64+1;j<x2/64;j++)a[i][j]=~a[i][j]; if(x/64==x2/64) { a[i][x/64]^=~0LL^(1LL<<(x&63))-1; a[i][x/64]^=~0LL^(1LL<<(x2&63))-1; } else { a[i][x/64]^=~0LL^(1LL<<(x&63))-1; a[i][x2/64]^=(1LL<<(x2&63))-1; } } } else { scanf("%d%d",&x,&y); y--,x--; printf("%d\n",!!(a[y][x/64]&1LL<<(x&63))); } } puts(""); } return 0; }
多分こなれてくるともっとスマートに書けるのではないかと……
