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;
}