PKU演習問メモ(4/26)
見出しのデザインを変えてみた。反映されてるのだろうか。
とりあえず手許のOpera(9.x),Safari(4.0.x),Firefox(3.6.x)だと意図した通りに表示される。
No. | Title | 分類・解法 | 主観的難易度 |
---|---|---|---|
2505 | A multiplication game | 二人零和有限確定完全情報ゲーム | ★★★☆☆ |
3088 | Push Botton Lock | 場合の数・動的計画法 | ★★☆☆☆ |
2956 | Repeatless Numbers | 順列 | ★★★☆☆ |
以下問題概要解法ソースコード
2505 A multiplication game
問題概要
p=1からはじめて、二人が交互にpに2から9のいずれかの整数をかけていき、最初にpをn以上にしたほうが勝ちというゲームを考える。
n(<42億)が与えられたとき、先手後手が互いに最善をつくすと仮定して、どちらが勝つかを求めよ。
解法
「いくつの数字をつくれば勝ちか」というのを考えていく。
たとえばn=1000ならp=111をつくれば、次のプレイヤーが何を掛けても111を作ったプレイヤーの勝ちである。
これを一般化して、nに9をかけても届かず、18をかければ届くような数(の範囲)を順次生成していけばよい。
AC数を見るに普通の人にはきっと簡単な問題だと思うんだけど、僕がゲーム系の問題が凄く苦手なため「主観的」難易度はかなり高めに設定。
ソースコード
int main() { ll n; while(cin>>n) { ll lo=n,hi=n; while(9<lo&&9<hi) { hi=lo/9-(lo%9==0); lo=(ll)ceil(lo/18.0); lo=max(lo,(ll)ceil(hi/2.0)); } cout<<(2<=lo&&lo<=9||2<=hi&&hi<=9?"Stan":"Ollie")<<" wins."<<endl; } return 0; }
3088 Push Botton Lock
問題概要
1番からB番までのB個のボタンのついた鍵がある。
鍵に対して、「まだ押してないボタンを同時にいくつか押す」操作を組み合わせることで、鍵を開ける方法を作ることができる。
Bが与えられたとき、鍵をあける方法の総数を答えよ。
解法
例えばB=2に対しては以下の操作が考えられるので、鍵の開け方の総数は25通りである。
- 123同時押し(1通り)
- 12のように二つを押す(3C2通り)
- 12のように二つを押す、その後残り一つを押す(3C2通り)
- 1のように一つを押す(3通り)
- 1のように一つを押した後、二つを押す(3通り)
- 1のように一つを押したあと、2のように一つを押す(3*2通り)
- 1のように一つを押したあと、2のように一つを押し、残り一つを押す(3*2通り)
これを一般化し、ある状態から(残りn個としよう)i個を押すような操作を全て再帰で考えてみる。
i個押す操作はi個の選び方(nCi通り)とn-i個の残りの選び方(rec(n-i)通り)の積である。
また、その時点で操作を終える場合の数が1通りある。
以上をそれぞれ足してやれば求める場合の数になるが、初期状態から操作しないという開け方は許されていないので、最後に答えから1を引いてやる。
あとは32bitでは答えが収まらないことに注意して再帰を実装すればいい。メモ化しなくとも計算時間は大丈夫な気はする(試してない)
ソースコード
ll C(int n,int k) { ll ret=1; if(n-k<k)k=n-k; rep(i,k)ret*=n-i; rep(i,k)ret/=i+1; return ret; } ll memo[12]; ll rec(int c) { if(c==0)return 1; if(memo[c])return memo[c]; ll ret=1; rep(i,c)ret+=rec(c-i-1)*C(c,i+1); return ret; } int main() { int CS; cin>>CS; rep(cs,CS){ int b; cin>>b; ll ans=rec(b)-1; cout<<cs+1<<" "<<b<<" "<<ans<<endl; } return 0; }
2956 Repeatless Numbers
問題概要
各桁に同じ数が2度以上現れない数を"repeatless number"と呼ぶことにする。
"repeatless number"を小さい順に書くと1,2,3,...,9,10,12,13,...,20,21,23,...のようになる。
n番目(n≦1000000)の"repeatless number"を求めよ。ただし1番目のrepeatless numberは1である。
解法
100万なので全列挙でも行ける……のだろうかと思って全列挙しようとしたらSegmentation faultしたorz
上手くやれば全列挙する方針でも解けるのかもしれない。
順列のn番目を求める問題。なれてないので非常に時間がかかった。よって主観的難易度は3.
方針としては、最初に桁数を求め、次に残りの部分の個数を順次引いていけばよい。って言うのは簡単なんだけど……コードがややこしい……orz
ソースコード
int P(int n,int k) { int ret=1; rep(i,k)ret*=n-i; return ret; } int cnt(int r,int d) { return (r-1)*P(r-1,d-1); } int main() { int n; while(cin>>n,n) { int d=1; for(;cnt(10,d)<n;d++)n-=cnt(10,d); vi ans; int r=10; bool use[10]={0}; rep(i,d) { int c=0; while(P(9-i,d-i-1)<n)n-=P(9-i,d-i-1),c++; int j=0; for(;j<10;j++)if(!(i==0&&j==0)&&!use[j])if(c--==0)break; use[j]=1; ans.pb(j); } fr(i,ans)cout<<*i; cout<<endl; } return 0; }