PKU演習問メモ(4/29) - simezi

No.	Title	分類・解法	主観的難易度
3193	Cow Phrasebook	文字列操作・二分探索	★★★☆☆
3199	Uncle Jack	多倍長整数演算	★☆☆☆☆
2506	Tiling	多倍長整数演算・動的計画法	★★☆☆☆
2657	Comfort	実装問題	★☆☆☆☆

問題概要ソース（ｒｙ

3193 Cow Phrasebook

問題概要

文字列の辞書m行(m≦1000)とフレーズn個(n≦10000)が与えられる。
フレーズのうち、辞書の文字列のどれかの接頭辞（辞書の文字列が、フレーズに完全に一致する文字列からはじまる）になっているものの個数を答えよ。

解法

statusにTLEが多いのでStringを使ったり、線形探索をしたりするとTLEになるっぽい（試してない）
Cの文字列を使用し、辞書のある文字列の接頭辞かどうかの判定には二分探索を用いればよい。以下実装例。

ソースコード

struct S{
	char str[61];
	S(){}
	S(const char *s)
	{
		strcpy(str,s);
	}
	bool operator<(const S &r)const
	{
		return strcmp(str,r.str)<0;
	}
};

int m,n;
S fb[1000];

int main()
{
	scanf("%d%d ",&m,&n);
	rep(i,m)
	{
		char s[61]; gets(s);
		fb[i]=S(s);
	}
	sort(fb,fb+m);
	
	int ans=0;
	rep(i,n)
	{
		char s[61]; gets(s);
		int p=lower_bound(fb,fb+m,s)-fb;
		if(strncmp(fb[p].str,s,strlen(s))==0)ans++;
	}
	cout<<ans<<endl;
	
	return 0;
}

strncmpなんて関数初めて知った。

3199 Uncle Jack

問題概要

n（≦10)枚のCDをd（≦25）人の甥に配るときの場合の数を求めよ。
n枚のCDとd人の甥は互いに区別があり、1枚もCDを貰わない甥がいても良い。

解法

n^dが求める場合の数である。最大ケースが10^25でlong longに収まらないので多倍長計算が必要。C++の人は頑張って自作。Javaの人はBigIntegerを使う。

ソースコード

import java.math.*;
import java.util.*;

class Main {

	public static void main(String[] args) {
		new Main().new pku3119().run();
	}
	class pku3119{
		void run(){
			Scanner sc=new Scanner(System.in);
			for(;;){
				int n=sc.nextInt(),d=sc.nextInt();
				if(n==0&&d==0)break;
				
				BigInteger ans=BigInteger.ONE;
				for(int i=0;i<d;i++)
ans=ans.multiply(BigInteger.valueOf(n));
				System.out.println(ans);
			}
		}
	}
}

2506 Tiling

問題概要

2xn(n≦250)の長方形を1x2の長方形と2x2の正方形のタイルを使って隙間なく敷き詰めるときの場合の数を求めよ。

解法

タイルがi枚の時の場合の数をa[i]とおくとa[i]=a[i-1]+a[i-2]*2.
この漸化式を実装すればいいが、答えが大きいので多倍長計算が必要。

ソースコード

class Main {

	public static void main(String[] args) {
		new Main().new pku2506().run();
	}
	class pku2506{
		void run(){
			Scanner sc=new Scanner(System.in);
			while(sc.hasNextInt()){
				
				int n=sc.nextInt();
				
				BigInteger[] dp=new BigInteger[n+2];
				dp[0]=BigInteger.ONE; dp[1]=BigInteger.ONE;
				
				for(int i=2;i<=n;i++)
dp[i]=dp[i-1].add(dp[i-2].multiply(BigInteger.valueOf(2)));
				
				System.out.println(dp[n]);
			}
		}
	}
}

(importは省略)

2657 Comfort

問題概要

円周上に時計回りに1からnの点がある。1の点からスタートして、時計回りの方向のみに幅kのジャンプを繰り返して目的地zの点に着きたい。
点のうち与えられたm個には障害物があり進入することはできない。m個の点の番号がそれぞれ与えられたとき、ゴールにたどり着けるような最小のジャンプの幅kを求めよ。
ゴールの点とスタートの点に障害物があることはない。

解法

小さい幅から順にシミュレートすればいい。TLEが多いので時間が厳しいのかなと思ったら別にそんなことはなかった。単に無限ループを見落としてる人が多いみたい。

障害物にぶつかるorループしてたらそのジャンプ幅では失敗。

ソースコード

int n,z,m;
bool obs[1000];

bool ck(int s)
{
	int c=0;
	bool V[1000]={0};
	while(!obs[c]&&!V[c])
	{
		if(c==z)return 1;
		V[c]=1;
		c+=s; if(c>n)c-=n;
	}
	return 0;
}

int main()
{
	cin>>n>>z>>m; z--;
	rep(i,m)
	{
		int t; cin>>t;
		obs[t-1]=1;
	}
	int ans=1;
	for(;ans<n-1;ans++)if(ck(ans))break;
	cout<<ans<<endl;
	
	return 0;
}