PKU演習問メモ(2010/3/30)

今日通した問題メモ。
2389解いてて思ったけど、TopCoderのMarathon MatchとかでC++使ってる人はみんなどうやって巨大整数実装してるんだろう。乗算とかはやっぱりカラツバ法とかFFTとか使って高速化してるのだろうか。その昔妖精現実というサイトにJavaScriptで1024bitの公開鍵暗号（RSA）を実装とかいう企画があったけど、一月くらいで巨大整数クラスの速度を100倍くらい（記憶曖昧）にしてしまったあの怒涛の高速化は凄かった。高校生くらいの時にあれみて、当時プログラミングはできなかったけどライブラリがどんどん高速化していく開発ログ読んで感動した覚えがある。

て、ていうか妖精現実の中の人（は多分複数）競技プログラミングひょっとしたら今やってたりするのかもなあ。

1363 Rails

スタックを使って1,2,3,...,nの数列を与えられた順番に並び替えられるかという問題。入出力の形式がちょっと変わってる。

2393 Yogurt factory

n週間ヨーグルトを製造する。i週目にヨーグルトを1単位生産するのにかかるコストc[i]、n週目に出荷しなければならないヨーグルトy[i]の量が与えられる。容量無限の倉庫を使って1週間あたり1単位のヨーグルトをコストSで保管できるとき、合計コストの最小値を求めよという問題。動的計画法っぽいと思ったけど良く考えたら貪欲法だった。

2304 Combination Lock

金庫のダイアルをシミュレーションして合計の回す角度を求める問題。

2389 Bull Math

40桁×40桁の掛け算をせよという問題。手許のPCにJavaの環境がないのでC++で無理矢理書いた……

2390 Bank Interest

複利の計算。掛け算すればおk.compoundは複利で利息がつくという意味があるらしい。

2406 Power Strings

与えられた文字列(長さ100万以下）がn回の繰り返しになっているような最大のnを求める問題。

2456 Aggressive cows

n個の点x[i]からc個を選ぶとき、|x[i]-x[j]|の最小値の最大値はいくらかという問題。二分法で求めれば良い。整数インデックスの二分法苦手なんだよな……一回WA出した……

2453 An Easy Problem

整数iが与えられたときiとjを二進法で表したとき同じ数の1を含み、かつi＜jであるような整数jを求めよという問題。なんか去年出たショートコーディング本にこの問題の解説あったなｗ

2498 StuPId

生徒のID番号の一桁が?になっているので復元する問題。ISBNと同じように?を0-9に置き換えてvalidか確かめれば良い。

2696 A Mysterious Function

メモ化再帰を書けという問題。メモに代入忘れてハマったアホがここに一人。

これで296問。

1363 Rails

int n,t[1000];

bool solve()
{
	int r=1;
	stack<int> S;
	
	rep(i,n)
	{
		while(t[i]>=r)S.push(r++);
		
		if(t[i]!=S.top())return 0;
		S.pop();
	}
	return 1;
}

int main()
{
	bool f=1;
	while(cin>>n,n)
	{
		if(!f)cout<<endl; f=0;
		
		while(cin>>t[0],t[0])
		{
			rep(i,n-1)cin>>t[i+1];
			cout<<(solve()?"Yes":"No")<<endl;
		}
	}
	return 0;
}

2406 Power Strings

char str[1000001];

int main()
{
	while(gets(str),strcmp(str,"."))
	{
		int len=strlen(str),ans=1;
		
		for(int l=1;l<=len/2;l++)if(len%l==0)
		{
			int t=len/l;
			for(int i=1;i<t;i++)rep(j,l)
			if(str[i*l+j]!=str[j])goto NEXT;
			
			ans=t; break;
			NEXT:;
		}
		
		printf("%d\n",ans);
	}
	return 0;
}

IOのコストがでかいのでcinを使うとTLEになる。（らしい、試してない）

2456 Aggressive cows

int n,c,p[100000];

int main()
{
	scanf("%d%d",&n,&c);
	rep(i,n)scanf("%d",p+i);
	sort(p,p+n);
	
	int l=1,h=p[n-1]-p[0],mid,ans;
	while(l<=h)
	{
		mid=(l+h)/2;
		int cur=0,ok=1;
		rep(i,n)if(p[i]-p[cur]>=mid)ok++,cur=i;
		
		if(ok>=c)l=(ans=mid)+1;
		else h=mid-1;
	}
	cout<<ans<<endl;
	
	return 0;
}

混乱したのでansの変数を導入した。どういう書き方が簡潔なんだろう。