PKU演習問メモ(9/12)

PKU

ICPC合宿組うらやましいなあ。


やっぱ競技プログラミングなんて才能9割じゃねーの。
努力しても超えられない壁ばっかだ。

No. 問題名 問題の種類および解法 難易度
3138 ACM Team Selection 実装 ★☆☆☆☆
3095 Linear Pachinko 確率・期待値 ★★☆☆☆
3105 Expectation 数え上げ・期待値 ★★★★☆

3138 ACM Team Selection

問題概要

preliminaryコンテストの結果が与えられるとき、on-siteへ出場するチームの数を求めよ。

on-siteに出場できるチームは1校につき3チームまでで、以下の条件を満たした数に等しい。

  • preliminaryでM問を解いたチームが一つ以上ある
  • 前年度World Finalsで20位以内に入ったチームがある
  • ローカルコンテストの主催校である
解法

これ問題文が意味不明すぎるんじゃないか？
各学校につきいくつ条件を満たすかを求め、それを合計すればいいのだけど、そうは読み取れない気がする。

ソースコード
int s,t,m;
bool p[101],q[101],r[101];

int main()
{
	int cs=0;
	while(scanf("%d%d%d",&s,&t,&m),s)
	{
		rep(i,s+1)r[i]=0;
		rep(i,s)
		{
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			p[a]=b; q[a]=c;
		}
		rep(i,t)
		{
			int a,b;
			scanf("%d%d",&a,&b);
			if(b>=m)r[a]=1;
		}
		
		int ans=0;
		rep(i,s+1)ans+=p[i]+q[i]+r[i];
		printf("Case %d: %d\n",++cs,ans);
	}
	return 0;
}

3095 Linear Pachinko

問題概要

一次元でのパチンコを考える。

_._/\_|.__/\./\_

のような地形のそれぞれの場所に、それぞれ等確率でパチンコ玉が降ってくる。
_に落ちた玉はその場で止まり、
.に落ちた玉は穴に入り、
/に落ちた玉は左へ転がり続け、地形の外に出るか、穴に落ちるか、\もしくは|に当たるまで動き続ける。
\に落ちた玉は左右が逆で同様。
|に落ちた玉は、50%の確率で/または\に落ちたのと同じことが起こる。


このとき、玉が穴に入る確率を求めよ。

解法

問題文にしたがってシミュレートすればよい。具体的実装はコードを参照。

ソースコード
int l;
char in[99];

int main()
{
	while(scanf("%s",in),in[0]!='#')
	{
		l=strlen(in);
		double ans=0;
		
		rep(i,l)
		{
			if(in[i]=='.')ans+=1.0/l;
			if(in[i]=='/'||in[i]=='|')
			{
				bool f=1;
				for(int p=i-1;p>=0;p--)
				{
					if(in[p]=='.')break;
					if(in[p]=='|'||in[p]=='\\')
					{
						f=0; break;
					}
				}
				if(f)ans+=(in[i]=='|'?0.5:1.0)/l;
			}
			if(in[i]=='\\'||in[i]=='|')
			{
				bool f=1;
				for(int p=i+1;p<l;p++)
				{
					if(in[p]=='.')break;
					if(in[p]=='|'||in[p]=='\\')
					{
						f=0; break;
					}
				}
				if(f)ans+=(in[i]=='|'?0.5:1.0)/l;
			}
		}
		printf("%d\n",(int)(ans*100));
	}
	return 0;
}

3105 Expectation

問題概要

0以上n-1以下のランダムな整数を返す乱数生成器がある。
この生成器を（独立に）二つくっつけ、xorを取ったものを全体の出力とする。
全体の出力の期待値を求めよ。


n≦10^9を満たす。

解法

なぜか言語C++だとACでG++だとPE.PEって意味不明。
両者でビットシフトの演算の挙動が違ったような気がしなくもないんだけど、PEは原因が想像もつかない。


各ビットについて、0になる確率と1になる確率をO(1)で求めることが出来れば、O(log n)で答えが求まる。
iビット目が1になっている出力は、生成器A,Bのその桁の出力が(0,1)または(1,0)の場合。
よってn未満でiビット目が1であるような整数の個数を求めればよい。（求めればone*(n-one)/(n*n)が全体の出力でその桁が1になる確率となる）


n未満でiビット目が1であるような整数はいくつあるかというと、
nが

10101(1)101010

みたいな場合（括弧のところがiビット目）
括弧より右の選び方が6桁分、括弧より左の部分が5桁分になる。
よってそれらを掛け合わせればよい。
また、括弧の中が1の場合、10101(1)で始まるような数も候補に入るので、
101010以下の整数の数が候補に足される。

ソースコード
int calc(int n,int k)
{
	int ret=0;
	if(n&1<<k)ret+=(n&(1<<k)-1)+1;
	ret+=(n>>k+1)*(1<<k);
	return ret;
}
int main()
{
	int n,cs; scanf("%d",&cs);
	while(cs--)
	{
		scanf("%d",&n);
		double ans=0;
		for(int i=0,m=n;m;i++,m/=2)
		{
			int one=calc(n-1,i);
			ans+=pow(2.0,i+1)*one*(n-one);
		}
		ans/=1.0*n*n;
		printf("%.5f\n",ans);
	}
	return 0;
}