PKU演習問メモ（2010/3/25）

PKU

さて今日も易しめなの適当に解こう。

2002 Squares
与えられた点の集合の中から正方形の数を数える。二点とって残りの二点を二分探索で探すO(n^2log n)の解法で間に合う。（上位は1桁速いのでもっと高速なアルゴリズムあるのかな？）
2042 Lagrange's Four-Square Theorem
与えられた整数nを4つ以下の平方数の和として表す場合の数は何通りか求める（順番は考慮しない）。たしかAOJにもあった問題。こっちだとTLE厳しいのかと思ったけど同じようにa≧b≧c≧dの条件つけて再帰でおｋだった。
2941 Homogeneous Squares
与えられたnn行列(n≦1000）の、行列式を書き下したときにその各項の値が全て同じかどうかを判定する問題。行ごとの差分、列ごとの差分をそれぞれ調べればよい。入力が大きいのでうっかりストリーム入出力を使うとTLEになる。
2081 Recaman's Sequence
次の漸化式で定義される数列a[i]のn番目の項を求める問題。a[i]=a[i-1]-i（a[i-1]>iかつa[i]の数字がa[0]からa[i-1]に存在しないとき）そうでないならa[i]=a[i-1]+i．でた数字をいくらまで覚えればいいのかよくわからなかったが適当に300万まで配列とったらACだった（酷
2136 Vertical Histogram
文字の分布を数えてヒストグラムを書く。
2190 ISBN
ISBN番号のうち1桁が？になっている。これを復元する。？を0から9まで順に置き換えてvalidかどうか調べればよい。最後の一桁が？だったらX(10)も調べる。……にしても破壊力のある問題文だ。Farmer John's cows enjoy reading books, and FJ has discovered that his cows produce more milk when they read books of a somewhat intellectual nature. He decides to update the barn library to replace all of the cheap romance novels with textbooks on algorithms and mathematics.（ジョンの飼ってる牛は読書が好きである。彼は牛が自然科学の本を読むと取れるミルクの量が増えることを見つけた。彼は畜舎の本棚のやすっぽいロマンスの本をすべてアルゴリズムと数学の本に入れ替えることにした。）あれですか、この（以下検閲削除
2229 Sumsets
与えられた数n（n≦1000000）を2のべき乗の和で何通りに表せるか（同じ数を2度以上使ってよく、順番は区別しない）の場合の数の下9桁を求める問題。a[0]≧a[1]≧……の条件を入れたメモ化探索で通った。前に解いてREったとき下9桁っての見落としてたような気がしてきた……ボトムアップな動的計画法だとタイム1/10くらいになるんだろうか。
2309 BST
図のような（本家参照）無限の大きさの二分木のうちあるノードが与えられる。そのノードの子のうち最小と最大の大きさのノードの値を求める問題。与えられた数が木の下から何段目かを見れば最大値と最小値の差がわかる。すると、与えられた数は最大値と最小値の平均になっているので答えがわかる。
2316 SPIN
自転車のダイアル式ロックのようなのの動作をシミュレートする問題。読解に時間かかってしまった……
2329 Nearest number - 2
NxN行列の0成分について、マンハッタン距離でもっとも近い非0成分が一つだけあるならそれに置換、二つ以上あるならそのままにするという変換を施すという問題。O(N^4)の解法だとあからさまにTLEになりそう（試してない）なので、非0成分を全部覚えてそれを線形探索して距離が最小の成分を求める方針にしたら通った。O(MN^2)：Mは疎な成分の数。JavaだとO(N^4)の解法でも通る気が凄まじくする……制限時間3倍だから15秒も使えるし……
2362 Square
2002とタイトルが似すぎｗ別記事で解説書こう。
2363 Blocks
辺が1インチのn個（n≦1000）の立方体のブロックを表面積が最小になるように直方体に組み上げる時の、最小の表面積を求める問題。a≦b≦cの制限つけて全探索でおｋ.
2385 Apple Catching
T分の間1分毎に二つのどちらかからりんごの落ちる2本の木がある。落ちるりんごの木の番号と移動回数Wが与えられたとき、W回以下の移動で取れる最大のりんごの数を求めよという問題。動的計画法で解けばいい。
2387 Til the Cows Come Home
ダイクストラ法……の少しいじわるな問題。エッジに重複があるorz

これで245問。


以下面白かった問題のソースコード。

2002 Squares

int n;
pi pt[2000];

int main()
{
	while(cin>>n,n)
	{
		rep(i,n)
		{
			int a,b; cin>>a>>b;
			pt[i]=mp(a,b);
		}
		sort(pt,pt+n);
		
		int cnt=0;
		rep(i,n)rep(j,i)if(pt[i]!=pt[j])
		{
			int dy=pt[j].second-pt[i].second,
				dx=pt[j].first-pt[i].first;
			pi pa=pt[i],pb=pt[j];
			pa.first-=dy,pa.second+=dx;
			pb.first-=dy,pb.second+=dx;
			
			if(binary_search(pt,pt+n,pa)&&binary_search(pt,pt+n,pb))cnt++;
		}
		cout<<cnt/2<<endl;
	}
	return 0;
}

STLが便利。STLやばい。マジやばい（以下略

2136 Vertical Histogram

int main()
{
	int dist[256]={0};
	
	char buf[80];
	while(cin>>buf)
	{
		for(int i=0;buf[i];i++)
		dist[buf[i]]++;
	}
	
	int mx=*max_element(dist+'A',dist+'Z'+1);
	rep(i,mx)rep(j,26)
		cout<<(dist['A'+j]>=mx-i?'*':' ')<<(j==25?'\n':' ');
	rep(i,26)cout<<char('A'+i)<<(i==25?'\n':' ');
	
	return 0;
}

('A'+i)←ドクオに見えて仕方ない。

2329 Nearest number - 2

int n,mtx[200][200],ans[200][200],nnz;
pi nz[40000];

int main()
{
	scanf("%d",&n);
	rep(i,n)rep(j,n)
	{
		int t; scanf("%d",&t);
		ans[i][j]=mtx[i][j]=t;
		if(t)nz[nnz++]=mp(i,j);
	}
	rep(i,n)rep(j,n)if(!mtx[i][j])
	{
		bool f=0; int md=inf,mi,mj;
		rep(k,nnz)
		{
			int d=abs(nz[k].first-i)+abs(nz[k].second-j);
			if(d<md)f=0,md=d,mi=nz[k].first,mj=nz[k].second;
			else if(d==md)f=1;
		}
		if(!f)ans[i][j]=mtx[mi][mj];
	}
	
	rep(i,n)rep(j,n)printf("%d%c",ans[i][j],j==n-1?'\n':' ');
	
	return 0;
}

それぞれヘッダ等は省略。

2387 Til the Cows Come Home

int t,n;
vector<pair<pi,int> > e;

int main()
{
	cin>>t>>n;
	e.reserve(t);
	
	rep(i,t)
	{
		int a,b,c; cin>>a>>b>>c;
		a--,b--;
		rep(k,2)
		{
			pi p=mp(a,b);
			
			bool f=0;
			rp(j,e)if(e[i].first==p)
			{
				if(e[i].second>c)e[i].second=c;
				f=1; break;
			}
			if(!f)e.pb(mp(p,c));
			swap(a,b);
		}
	}
	sort(all(e));
	
	//Dijkstra
	priority_queue<pi> Q; Q.push(mp(0,n-1));
	bool V[1000]={0};
	
	while(!Q.empty())
	{
		int cur=Q.top().second,cc=Q.top().first;
		Q.pop();
		
		if(V[cur])continue;
		V[cur]=1;
		if(cur==0)
		{
			cout<<-cc<<endl; break;
		}
		
		vector<pair<pi,int> >::iterator p,bg,ed;
		
		bg=upper_bound(all(e),mp(mp(cur,0),0));
		ed=lower_bound(all(e),mp(mp(cur,n-1),inf));
		
		for(p=bg;p<ed;p++)if(!V[p->first.second])
			Q.push(mp(cc-p->second,p->first.second));
	}
	
	return 0;
}

Memory Limit Exceededおこしまくって、原因わからず辺リストを初めて使った。実際は別の場所がバグってただけだったので使う必要はなかった。（隣接行列or隣接リストでおｋ）
このコード書いた経験がいつかコンテストで役にたってほしいorz