PKU演習問メモ(8/15)

もっと頑張らないとなあorz

No.	問題名	問題の種類および解法	難易度
3219	Binomial Coefficients	素因数の個数・二項係数	★★☆☆☆
3191	The Moronic Cowmpouter	基数変換・マイナス二進数	★★☆☆☆
3185	The Water Bowls	探索	★★☆☆☆
3050	Hopscotch	探索	★★☆☆☆
2718	Smallest Difference	探索	★★★☆☆
2629	Common permutation	文字列	★★☆☆☆
2545	Hamming Problem	整数・再帰	★★☆☆☆
2537	Tight words	動的計画法	★★☆☆☆
2527	Polynomial Remains	多項式の計算	★★☆☆☆

3219 Binomial Coefficients

問題概要

与えられた整数n,kに対してnCkを2で割った余りを出力せよ。

0≦n,k≦2000000000を満たす。

解法

nCk = n!/(n-k)!/k!であるため、n!,(n-k)!,k!をそれぞれ素因数分解したときの2の指数を加減することでnCkの2の指数はわかる。

階乗の指数を求めるのは受験数学などでおなじみの定石がある。（[a/n]+[a/n^2]+……）

ソースコード

int n,k;
ll calc(int a)
{
	ll ret=0;
	for(;a;a/=2)ret+=a/2;
	
	return ret;
}

int main()
{
	while(~scanf("%d%d",&n,&k))
	{
		printf("%d\n",calc(n)-calc(n-k)-calc(k)==0);
	}
	return 0;
}

3191 The Moronic Cowmpouter

問題概要

通常の二進法は数をa0 + 2*a1 + 2^2*a2 + ……と表す。(aiは1または0）
次のようなマイナス二進法を考える。
a0 + (-2)*a1 + (-2)^2*a2 + ……　(aiは1または0）

マイナス二進数では、+-の符号を使うことなしに正負の数を表現できる。

与えられた十進法の数をマイナス二進法で表せ。
入力される数の絶対値は20億以下である。入力が0の場合は0と出力せよ。

解法

1の位が0か1か確定させることを考える。
(-2)以上の位がどうであれ、1の倍数を作ることはできないので、与えられた数を割った余りが1なら1の位は1である。

上の位も同様の考え方にしたがって、その一つ上の位の数の余りが0になるよう数を立てていけば、マイナス二進法での表記を求めることができる。

ソースコード

int main()
{
	int n,len=0;
	scanf("%d",&n);
	if(!n)
	{
		puts("0"); return 0;
	}
	
	ll m=n; char ans[200];
	for(ll i=1;m;i*=-2)
	{
		if(m%(i*2)!=0)
		{
			ans[len]='1';
			m-=i;
		}
		else ans[len]='0';
		len++;
	}
	reverse(ans,ans+len); ans[len]=0;
	puts(ans);
	
	return 0;
}

3185 The Water Bowls

問題概要

20個の0,または1の列が与えられる。
数字を一ヶ所選び、その左右を含めた三つ（端は二つ）の数字について、
0と1を反転させる操作ができる。

全ての数字を0にするために必要な操作の最低回数を求めよ。
初期状態から全ての数字を0にできる操作が存在することは保証されているとしてよい。

解法

ライツアウト1次元版。
左端の二つをひっくり返すか返さないかを決めれば後の返し方は一意に定まる。

ソースコード

int a[20],b[20];

int main()
{
	rep(i,20)scanf("%d",a+i);
	
	int ans=inf;
	rep(k,2)
	{
		int cnt=0;
		rep(i,20)b[i]=a[i];
		
		if(k)
		{
			cnt=1; b[0]^=1; b[1]^=1;
		}
		
		rep(i,19)if(b[i])
		{
			cnt++;
			rep(j,3)if(0<=i+j&&i+j<20)b[i+j]^=1;
		}
		rep(i,20)if(b[i]==1)cnt=inf;
		
		ans=min(ans,cnt);
	}
	printf("%d\n",ans);
	
	return 0;
}

3050 Hopscotch

問題概要

5x5のグリッドのそれぞれに一桁の数字が書かれている。
グリッドの一箇所から駒をスタートして、書かれている数字を末尾に加えながら、上下左右に一歩ずつ駒を進めていき、6桁の数を作る。
できた数字には先頭にゼロがあってもかまわない。

このとき異なる数をいくつ作ることができるか求めよ。

解法

DFSしてセットに入れて数えればよい。6桁なので特に工夫をしなくても間に合う。

ソースコード

int dy[]={-1,0,1,0},dx[]={0,1,0,-1};
int hop[5][5];
set<int> S;

void rec(int y,int x,int c,int n)
{
	if(n==6)
	{
		S.insert(c); return;
	}
	rep(d,4)
	{
		int ny=y+dy[d],nx=x+dx[d];
		if(ny<0||ny>=5||nx<0||nx>=5)continue;
		rec(ny,nx,c*10+hop[ny][nx],n+1);
	}
}

int main()
{
	rep(i,5)rep(j,5)scanf("%d",hop[i]+j);
	rep(i,5)rep(j,5)rec(i,j,hop[i][j],1);
	
	printf("%d\n",S.size());
	
	return 0;
}

2718 Smallest Difference

問題概要

重複しない0から9までの数の集合が与えられる。
これらを好きに二つに分け、それぞれで全ての数字を一度ずつ使って整数を作る。leading zeroは許されない。
（たとえば0 1 2 4 6 7から、10と2467などが作れる）

二つの数字の差の絶対値の最小値を求めよ。

解法

数字は10個なので部分集合を全部列挙して、それぞれを並べ替えはちょっと無理。
二つの数字の桁数が異なる場合、桁数の多いほうを昇順に、桁数の少ないほうを降順にするのが最適解だとわかる。

二つの数字の桁数が同一の場合、先頭の数字が大きいほうは残りを昇順、小さいほうは残りを降順にするのが最適解。
先頭の数字は25通りしかありえないので全部試せばよい。

ソースコード

てきとーに場合分けしてたら冗長になってしまった気がする。

int sol(int *a,int na,int *b,int nb)
{
	if(na!=nb)
	{
		if(na>nb)
		{
			reverse(b,b+nb);
			if(na>1&&a[0]==0)swap(a[0],a[1]);
		}
		else
		{
			reverse(a,a+na);
			if(nb>1&&b[0]==0)swap(b[0],b[1]);
		}
		
		int x=0,y=0;
		rep(i,na)x*=10,x+=a[i];
		rep(i,nb)y*=10,y+=b[i];
		return abs(x-y);
	}
	int ret=inf;
	rep(i,na)rep(j,nb)
	{
		int A[10],B[10],x=0,y=0;
		rep(k,10)A[k]=a[k],B[k]=b[k];
		swap(A[0],A[i]); swap(B[0],B[j]);
		
		if(na>1&&A[0]==0||nb>1&&B[0]==0)continue;
		
		if(A[0]>B[0])sort(A+1,A+na),sort(B+1,B+nb,greater<int>());
		else sort(B+1,B+nb),sort(A+1,A+na,greater<int>());
		
		rep(k,na)x*=10,x+=A[k];
		rep(k,nb)y*=10,y+=B[k];
		ret=min(ret,abs(x-y));
	}
	return ret;
}

int main()
{
	int cs; scanf("%d ",&cs);
	while(cs--)
	{
		int d[10],n=0;
		char str[99]; gets(str);
		for(int i=0;str[i];i++)if(isdigit(str[i]))d[n++]=str[i]-'0';
		
		int ans=inf;
		rep(i,1<<n-1)
		{
			int a[10],b[10],na=0,nb=0;
			rep(j,n-1)
			{
				if(i&1<<j)a[na++]=d[j];
				else b[nb++]=d[j];
			}
			a[na++]=d[n-1];
			ans=min(ans,sol(a,na,b,nb));
		}
		printf("%d\n",ans);
	}
	return 0;
}

2629 Common permutation

問題概要

英小文字からなるそれぞれ長さ1000以下の二つの文字列a,bが与えられる。以下のような文字列xのうち最長のものを出力せよ。

• xのある順列はaの部分文字列（必ずしも連続しない）である。
• xのある順列はbの部分文字列（必ずしも連続しない）である。

このような文字列が複数ある場合、アルファベット順で最初のものを出力せよ。

解法

xの「順列」が部分文字列になっているか、なのでアルファベットの出現回数のみが問題になる。
a,bのアルファベットの出現回数を数え、それぞれの文字について小さいほうの回数だけ出力してやればよい。

のだが入力に空行があるらしく、getsを使わないとWAになった。

ソースコード

char A[1001],B[1001];

int main()
{
	while(gets(A),gets(B))
	{
		int a[256]={0},b[256]={0};
		for(int i=0;A[i];i++)a[A[i]]++;
		for(int i=0;B[i];i++)b[B[i]]++;
		
		char ans[1001]={0}; int l=0;
		rep(i,256)rep(j,min(a[i],b[i]))ans[l++]=i;
		puts(ans);
	}
	return 0;
}

2545 Hamming Problem

問題概要

3つの素数p1,p2,p3に対する、ハミング数とは素因数がp1,p2,p3のいずれかのみからなる数を指す。
p1,p2,p3が与えられたとき、n番目に小さなハミング数を求めよ。

全ての入力、出力は10^18以下であることが保証されている。

解法

ハミング数は数が少ないので全て生成して間に合う。
（ただし重複して生成するのを避けるくらいの工夫は必要）

ソースコード

ll p[3],n;
vector<ll> H;

void gen(ll c,int use)
{
	if(c>1)H.pb(c);
	for(int i=use;i<3;i++)if(c*1.0*p[i]<=(ll)1e18)
	gen(c*p[i],i);
}

int main()
{
	cin>>p[0]>>p[1]>>p[2]>>n;
	gen(1,0);
	sort(all(H));
	cout<<H[n-1]<<endl;
	
	return 0;
}

2537 Tight words

問題概要

0以上k以下の数字がn個並んだもののうち、隣り合う数字の差の絶対値が1以下のものの割合を求めよ。

k≦9,n≦100を満たす。

解法

割合を求めよってちょっと新鮮。
mod〜で求めよと解法はほとんど一緒だけど。

dp[i][j]にi桁で最後の数字がjの数で条件を満たすものの割合を持つ。
すると漸化式が立てられるのでDPできる。

ソースコード

int n,k;
double dp[100][10];

int main()
{
	while(~scanf("%d%d",&k,&n))
	{
		rep(i,n)rep(j,k+1)dp[i][j]=0;
		
		rep(i,k+1)dp[0][i]=1;
		for(int i=1;i<=n;i++)
		{
			rep(j,k+1)for(int l=-1;l<=1;l++)if(0<=j+l&&j+l<=k)
			dp[i][j+l]+=dp[i-1][j]/(k+1);
		}
		double ans=0;
		rep(i,k+1)ans+=dp[n-1][i];
		printf("%.5f\n",ans/(k+1)*100);
	}
	return 0;
}

2527 Polynomial Remains

問題概要

多項式a0+a1x+a2x^2+……+anx^nを、x^k+1で割った余りを求め、指定された形式で出力せよ。
n,k≦10000である。

解法

ソースコード参照。余りが0の場合は0を出力することに注意。

ソースコード

int n,k,a[10001];

int main()
{
	while(scanf("%d%d",&n,&k),~n)
	{
		rep(i,n+1)scanf("%d",a+i);
		
		for(int i=n;i>=k;i--)if(a[i]!=0)
		{
			a[i-k]-=a[i]; a[i]=0;
		}
		
		int d=n;
		for(;d>0&&a[d]==0;d--);
		rep(i,d+1)printf("%d%c",a[i],i==d?'\n':' ');
	}
	return 0;
}