PKU演習問メモ(9/9)

PKU

今日のSRMの参加記は敗北記にしたくないなあ。
まあもっと問題解いてからぼやけって話だけど。

No. 問題名 問題の種類および解法 難易度
3172 Scales 枝刈り探索 ★★★☆☆
3175 Finding Bovine Roots 実装 ★★★☆☆
3181 Dollar Dayz 多倍長整数・動的計画法 ★★★☆☆

3172 Scales

問題概要

n個の錘がある。それぞれの重さはw[i]である。
これらを天秤の片側の皿にだけ載せて使い、重さを量りたい。
天秤はCより重いものを載せると壊れる。


n,w[i],Cが与えられたとき、天秤を使って量れる最大の重さを求めよ。


n≦1000,w[i]は31ビットの整数に収まるものとする。

解法

残りの錘をすべて使っても答えを更新できないなら枝を刈る枝刈り探索の方針。
なるべく枝を刈りたいので、

  • 重い錘から使う
  • 沢山錘を使う探索からはじめる

という工夫をすると良い。というかしないとTLE.

ソースコード
int n,c,w[1000];
ll ans,r[1001];

void dfs(int cur,ll s)
{
	if(r[cur]+s<=ans)return;
	
	ans=max(ans,s);
	if(cur==n)return;
	
	if(s+w[cur]<=c)dfs(cur+1,s+w[cur]);
	dfs(cur+1,s);
}
int main()
{
	scanf("%d%d",&n,&c);
	rep(i,n)scanf("%d",w+n-1-i);
	for(int i=n-1;i>=0;i--)r[i]=r[i+1]+w[i];
	
	dfs(0,0);
	printf("%lld\n",ans);
	
	return 0;
}

3175 Finding Bovine Roots

問題概要

nのbovine square rootをsqrt(n)の小数部分と定義する。
bovine square rootが与えられたn桁の数字で始まるような最小の整数を求めよ。


n≦9を満たす。

解法

適当なepsと答えの範囲の見積もりがかなり難しいと思うけどなあ。
答えがこのループの解法で求まることが保証されてたら難易度は★★くらい


long doubleを使ったが必要な精度がどれくらいかわからないので本当に必要だったかどうかわからない。


bovine square rootをyとすると元の数は(i+y)^2≦x＜(i+y+eps)^2を満たすような最小の整数xである。
(i+y)^2と(i+y+eps)^2の間に整数があるかどうかは、

  • (i+y)^2を切り上げ
  • (i+y+eps)^2を切り捨て

てやって、両者が一致するかどうかを見ればよい。

ソースコード
const ld INF=1e12,EPS=1e-14;

int main()
{
	int l,yi; scanf("%d%d",&l,&yi);
	
	ld eps=1,y=yi;
	rep(i,l)eps/=10,y/=10;
	
	for(int i=0;;i++)
	{
		ld l=i+y,r=i+y+eps;
		ll a=(ll)ceil(l*l),b=(ll)(r*r-EPS);
		
		if(a==b)
		{
			printf("%lld\n",a); break;
		}
	}
	
	return 0;
}

3181 Dollar Dayz

問題概要

nドルで$1,$2,...,$kドルのk種類の商品を買う組み合わせは何通りあるか。
nドルはぴったり使い切らなければならず、同じ商品を2つ以上買ったり、買わない商品があっても良い。

解法

典型的な動的計画法。
dp[i+1][j]にi番目までの商品を合計がjドルになるよう買う場合の数を入れ、表を更新していく。
[追記]この解法はO(nk^2)であるが、ぱない本によるとO(nk)まで計算量を落とすことができるようだ。

ソースコード
	class pku3181{
		int n,k;
		BigInteger[][] dp;
		void run(){
			Scanner sc=new Scanner(System.in);
			n=sc.nextInt(); k=sc.nextInt();
			dp=new BigInteger[n+1][k+1];
			for(int i=0;i<=n;i++)for(int j=0;j<=k;j++)dp[i][j]=BigInteger.ZERO;
			dp[0][0]=BigInteger.ONE;
			
			for(int i=1;i<=k;i++)for(int j=0;j<=n;j++)if(dp[j][i-1].compareTo(BigInteger.ZERO)>0)
			for(int k=j;k<=n;k+=i)dp[k][i]=dp[k][i].add(dp[j][i-1]);
			
			System.out.println(dp[n][k]);
		}
	}