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

今日はTopCoderSRM!
明日はCodeforcesのRound #6もある。
テンション上がる!

1106 Transmitters
半円の範囲をカバーするアンテナ一つと、いくつかの点がある。アンテナを回転させたときカバー範囲に入れられる点の最大値を求める問題。それぞれの点が半円の左右端にくる場合だけ調べれば十分。(送ったコードではちょうど正面の場合も調べていたorz)
1317 Do the Untwist
置換式暗号のシミュレート。Straight fowardに。
1331 Multiply
p,q,rが与えられたとき、掛け算p*q=rの成り立つ基数bを求める問題。bは16以下なので全探索でよい。
1318 Word Amalgamation
辞書が与えられる。次に単語が与えられる。それが辞書のなかのどれかの単語のアナグラムになっているとき、その辞書の単語を全て出力せよという問題。線形探索で通る。アナグラム判定はソートして同一になるかで調べると簡単に書ける。
1306 Combinations
二項係数を求める問題。答えはint型におさまることが保証されている。C(n,m)=C(n-1,m)+C(n-1,m-1)の漸化式を使って動的計画法で求めればいい。オーバーフロ対策などもしなくておk.
1496 Word Index
与えられた文字列が{a,...,z}の順列の何番目かを求める問題。TopCoderだったらnext_permutationでナイーブに全生成してるところw
1450 Gridland
NxMマスのグリッドの格子点にNM個の都市がある。都市から都市へは縦横斜めの8方に移動可能。このときの最短ハミルトン閉路を求める問題。都市の形がたいぶ特殊なので偶奇で場合分けするだけで最短路が直接もとまる。
1580 String Matching
文字列A,Bの、それぞれ連続する部分文字列a,bにおいてa[i]==b[i]となるような文字の個数の最大値を(common letters)とするとき(common letters)*2/(length(A) + length(B))を求めるという問題。一文字ずつずらして最大スコアを探せばよい。A.size()をint型にキャストしないままマイナス演算子つけたらバグって変なことになったorz.位置を演算するときは必ずint型にキャストするか代入しよう……
1575 Easier Done Than Said?
与えられた文字列が以下の規則を満たすか判定する問題。母音字が一つ以上含まれる、子音字または母音字が三つ連続で続かない、oo,ee以外の同一文字の連続がない。素直に実装すればおk.
1528 Perfection
与えられた数(6万以下)が完全数か、不足数か、過剰数かを判定する問題。数が小さいので1からn-1まで全部で試し割してよい。
1564 Sum It Up
与えられた数列a[i]の部分集合のうち和がtになるものを全てリストアップする問題。数列のサイズが最大12と小さいのでただの深さ優先探索で通る。
1468 Rectangles
各辺がx軸またはy軸に平行な長方形の座標の組がn個(n≦5000)与えられる。このなかで、「少なくとも他のひとつの長方形の内部に含まれている」長方形の数を求めよ、という問題。
1611 The Suspects
0からn-1番の生徒の中で、接触した生徒同士のグループm個が与えられる。0番の生徒が感染疑いであるとき、感染疑いの生徒は合計何人かを求める問題。感染疑いは推移する。
1666 Candy Sharing Game
n人の生徒がa[i]個(偶数)ずつキャンディを持って円形に座っている。1ターン毎に持っているキャンディの半分を右隣の人に渡し、個数が奇数になった生徒はキャンディを更に一個貰う。全員のキャンディの個数が同じになるまでこの操作を繰り返すシミュレーションをするという問題。デバッグコード残したままSubmitしてんのorz
1781 In Danger
k=2のヨセフス数を求める問題。wikipedia先生に一般解を聞いた。


260問。さすがに最近ちょっと頑張りすぎた……
疲れるばっかりであんまり身になっている気がしない。もっとこう、色々考えて解こう。まあでもとりあえずキリのいいとこで300問はやっておくか。

1106 Transmitters

int main()
{
	int x,y; double r2;
	while(cin>>x>>y>>r2,r2>=0)
	{
		int n; cin>>n;
		int px[n],py[n];
		rep(i,n)cin>>px[i]>>py[i],px[i]-=x,py[i]-=y;
		r2*=r2;
		
		int ans=0;
		rep(i,n)rep(k,3)
		{
			int cnt=0;
			
			int bx,by;
			if(k==0)bx=px[i],by=py[i];
			if(k==1)bx=py[i],by=-px[i];
			if(k==2)bx=-py[i],by=px[i];
			
			rep(j,n)
			{
				//a*b*cosθからcosθの符号がわかる
				double costab=bx*px[j]+by*py[j];
				
				int d2=px[j]*px[j]+py[j]*py[j];
				if(costab>-EPS&&d2<r2+EPS)cnt++;
			}
			ans=max(ans,cnt);
		}
		cout<<ans<<endl;
	}
	return 0;
}

久しぶりの幾何問な気がする。

1468 Rectangles

int main()
{
	while(cin>>n)
	{
		rep(i,n)
		{
			int a,b,c,d; cin>>a>>b>>c>>d;
			rect[i]=mp(mp(a,c),mp(b,d));
		}
		sort(rect,rect+n);
		
		int cnt=0;
		rep(i,n)
		{
			int xi,Xi,yi,Yi;
			xi=rect[i].first.first,
			yi=rect[i].first.second;
			Xi=rect[i].second.first,
			Yi=rect[i].second.second;
			
			if(i<n-1&&rect[i]==rect[i+1])
			{
				cnt++; continue;
			}
			
			bool f=0;
			rep(j,n)
			{
				int xj,Xj,yj,Yj;
				xj=rect[j].first.first,
				yj=rect[j].first.second;
				Xj=rect[j].second.first,
				Yj=rect[j].second.second;
				if(xi<xj)break;
				
				if(i!=j)
				if(xj<=xi&&Xi<=Xj)
				if(yj<=yi&&Yi<=Yj)
				{
					f=1; break;
				}
			}
			if(f)cnt++;
		}
		cout<<cnt<<endl;
	}
	return 0;
}

一応左端のx座標でソートしてループ回る回数を少なくしてみたけど、よくこれで通ったもんだ……(左端のx座標全部同じで、全く包含関係のないn=5000のテストケースがあったら確実にTLEw)

1781 The Suspects

int main()
{
	int n,m;
	while(cin>>n>>m,n)
	{
		queue<int> Q;
		bool V[m]; fill(V,V+m,0);
		set<int> G[m];
		
		rep(i,m)
		{
			int t,k; cin>>t;
			rep(j,t)
			{
				cin>>k,G[i].insert(k);
				if(k==0)Q.push(i);
			}
		}
		
		int ans=0;
		bool F[n]; fill(F,F+n,0);
		while(!Q.empty())
		{
			int cur=Q.front(); Q.pop();
			
			if(V[cur])continue;
			V[cur]=1;
			fr(i,G[cur])
			{
				if(F[*i])continue;
				F[*i]=1,ans++;
				rep(j,m)if(!V[j]&&G[j].count(*i))
					Q.push(j);
				
			}
		}
		cout<<(ans?ans:1)<<endl;
	}
	return 0;
}

グループをノードと見て幅優先探索してみた。