PKU演習問メモ(8/13)

No. 問題名 問題の種類および解法 難易度
1941 The Sierpinski Fractal 再帰フラクタル ★★★☆☆
1681 Painter's Problem 探索 ★★☆☆☆
1859 The Perfect Symmetry 幾何 ★★☆☆☆
1840 Eqs ハッシュ ★★★☆☆
1520 Scramble Sort 実装・文字列 ★☆☆☆☆
1329 Circle Through Three Points 幾何 ★★☆☆☆
1269 Intersecting Lines 幾何 ★☆☆☆☆
1152 An Easy Problem! 実装 ★☆☆☆☆
3660 Cow Contest 順序付け ★★★☆☆
1094 Sorting It All Out 順序付け ★★★☆☆
2785 4 Values whose Sum is 0 ハッシュ ★★★☆☆

1941 The Sierpinski Fractal

問題概要

シェルピンスキーのガスケットを指定されたフォーマットで描け。
n≦10とする。

解法

フラクタル図形の定石どおり再帰で描く。
再帰を1段深くするたびに三角形を3つ描いていく。


メモリ上で図形を全て描いてしまうとよい。(気がする)

ソースコード
char ans[10][1024][2049]; int pw[20];
void rec(int y,int x,int l,int out)
{
	if(l==1)
	{
		char *a=ans[out][y];
		a[x]='/'; a[x+1]=a[x+2]='_'; a[x+3]='\\';
		a=ans[out][y-1];
		a[x+1]='/'; a[x+2]='\\';
		return;
	}
	rec(y,x,l-1,out); rec(y,x+pw[l],l-1,out);
	rec(y-pw[l-1],x+pw[l-1],l-1,out);
}
int main()
{
	pw[0]=1; rep(i,19)pw[i+1]=pw[i]*2;
	for(int it=1;it<11;it++)
	{
		rep(i,pw[it])
		{
			rep(j,pw[it+1])ans[it-1][i][j]=' ';
			ans[it-1][i][pw[it+1]-pw[it]+i+1]=0;
		}
		rec(pw[it]-1,0,it,it-1);
	}
	
	int n;
	while(scanf("%d",&n),n)
	{
		rep(i,pw[n])puts(ans[n-1][i]);
		puts("");
	}
	
	return 0;
}

1681 Painter's Problem

問題概要

1x1のマスからなるnxnの正方形が与えられる。マスは黄色または白で、ある1マスを選んで塗りつぶす操作を行うと、そのマスおよびその上下左右のマスの色が反転する。


全てのマスを黄色にするのにかかる最短手数を求めよ。
n≦15以下とする。

解法

いわゆるライツアウト。最初の1列を決めれば後の手順は一意に定まる。
n≦15と小さいので、最初の1列として全てを試してよい。

ソースコード
int dy[]={-1,0,1,0,0},dx[]={0,1,0,-1,0};
int n;
bool sq[15][15],tmp[15][15];

void brush(int y,int x)
{
	rep(d,5)
	{
		int ny=y+dy[d],nx=x+dx[d];
		if(0<=ny&&ny<n&&0<=nx&&nx<n)tmp[ny][nx]^=1;
	}
}

int main()
{
	int cs; scanf("%d",&cs);
	while(cs--)
	{
		char c; scanf("%d",&n);
		rep(i,n)rep(j,n)scanf(" %c",&c),sq[i][j]=c=='w';
		
		int ans=inf;
		rep(bit,1<<n)
		{
			int cnt=0;
			rep(i,n)rep(j,n)tmp[i][j]=sq[i][j];
			rep(i,n)if(1<<i&bit)brush(0,i),cnt++;
			for(int i=1;i<n;i++)rep(j,n)if(tmp[i-1][j])brush(i,j),cnt++;
			
			rep(i,n)if(tmp[n-1][i])cnt=inf;
			ans=min(ans,cnt);
		}
		if(ans==inf)puts("inf");
		else printf("%d\n",ans);
	}
	return 0;
}

1859 The Perfect Symmetry

問題概要

平面上にn個の点が与えられる。
n個の点全てに、それぞれについて対称な点が存在するような、対称中心が存在するならその座標を求め、存在しない場合"This is a dangerous situation!"と出力せよ。

n≦20000とする。

解法

対称中心はΣp/n.
全ての座標を中心点を基準にした座標に直すと、
問題文の条件は、全てのiに対してpi=-pjなる点が存在することと同値。
これは、点をソートしたときpi=-pn-i-1かどうかを見ればよいことになる。

ソースコード
int n;
pair<double,double> p[20000];

int main()
{
	while(scanf("%d",&n),n)
	{
		int a,b; double sx=0,sy=0;
		rep(i,n)
		{
			scanf("%d%d",&a,&b);
			sx+=a; sy+=b; p[i]=mp(a,b);
		}
		sx/=n; sy/=n;
		rep(i,n)p[i].first-=sx,p[i].second-=sy;
		sort(p,p+n);
		
		bool fail=0;
		rep(i,(n+1)/2)
		if(abs(p[i].first+p[n-1-i].first)>EPS||
			abs(p[i].second+p[n-1-i].second)>EPS)
		{
			fail=1; break;
		}
		if(fail)puts("This is a dangerous situation!");
		else printf("V.I.P. should stay at (%.1f,%.1f).\n",sx,sy);
	}
	return 0;
}

1840 Eqs

問題概要

5つの整数、a1,a2……,a5が与えられる。
a1x1^3+a2x2^3+a3x3^3+a4x4^3+a5x5^3=0を満たす整数の組(x1,x2,x3,x4,x5)の
うち、-50≦xi≦50,xi!=0であるようなものの個数を求めよ。


また、-50≦ai≦50を満たす。

解法

動的計画法は値が大きくなり使うことが難しい。
枝刈り探索も上手く枝を刈ることが難しかった。


ので、ハッシュを使って探索した。
x1,x2,x3までで出来る整数を全て生成してハッシュに入れ、
x4,x5を使って出来る整数がその中にあるかどうかを調べる。


ハッシュはクラスにしたので以後使いまわす予定。

ソースコード
struct Hash{
	int size,A;
	int *key,*value;
	
	Hash(int size=9999991,int A=1007):size(size),A(A)
	{
		key=new int[size]; value=new int[size];
	}
	int func(unsigned int k)
	{
		return k*A%size;
	}
	int find(int k)
	{
		int i=func(k);
		for(;;)
		{
			if(key[i]==k&&value[i])break;
			if(!value[i])break;
			i++; if(i==size)i=0;
		}
		return i;
	}
	int get(int k)
	{
		int i=find(k);
		if(key[i]!=k)return 0;
		return value[i];
	}
	void set(int k,int v)
	{
		int i=find(k);
 		key[i]=k; value[i]=v;
	}
	int inc(int k)
	{
		int i=find(k);
		key[i]=k; return ++value[i];
	}
};

int main()
{
	int a[5];
	rep(i,5)cin>>a[i];
	
	Hash hash(5000003);
	for(int i=-50;i<=50;i++)if(i)
	for(int j=-50;j<=50;j++)if(j)
	for(int k=-50;k<=50;k++)if(k)
	{
		int s=a[0]*i*i*i+a[1]*j*j*j+a[2]*k*k*k;
		hash.inc(s);
	}
	int ans=0;
	
	for(int i=-50;i<=50;i++)if(i)
	for(int j=-50;j<=50;j++)if(j)
	{
		int s=a[3]*i*i*i+a[4]*j*j*j;
		ans+=hash.get(s);
	}
	cout<<ans<<endl;
	return 0;
}

1520 Scramble Sort

問題概要

" ,"で区切られた一行のリストが与えられる。
これらには数字または文字列が含まれる。
文字列は文字列で、数字は数字でソートし、元のリストで文字列だった場所には文字列を、数字だった場所は数字で出力せよ。
リストの終わりは行末の"."で表され、入力の終わりは"."のみからなる一行で表される。

解法

ソース参照。文字列のソートは辞書順なので注意。

ソースコード
bool isnum[100000];

bool cmp(string A,string B)
{
	string a,b;
	fr(i,A)a.pb(tolower(*i)); fr(i,B)b.pb(tolower(*i));
	if(a!=b)return a<b;
	return A<B;
}

int main()
{
	string line;
	while(getline(cin,line),line!=".")
	{
		fr(i,line)if(*i==','||*i=='.')*i=' ';
		
		int n=0;
		vi num; vector<string> str;
		stringstream ss(line);
		string tmp;
		while(ss>>tmp)
		{
			bool f=1;
			fr(i,tmp)if(isalpha(*i)){f=0;break;}
			
			isnum[n++]=f;
			if(f)
			{
				int t;
				stringstream sss(tmp); sss>>t;
				num.pb(t);
			}
			else str.pb(tmp);
		}
		sort(all(num)); sort(all(str),cmp);
		
		int i1=0,i2=0;
		rep(i,n)
		{
			if(isnum[i])cout<<num[i1++];
			else cout<<str[i2++];
			cout<<(i==n-1?".\n":", ");
		}
	}
	return 0;
}

1329 Circle Through Three Points

問題概要

同一直線状にはない3点の座標が与えられる。
これらを通る円の式を以下の二通りの形式で出力せよ

  • (x-p)^2 + (y-q)^2 = r^2
  • x^2 + ax + y^2 + by + c = 0
解法

spaghetti sourceのライブラリを使用(http://www.prefield.com/algorithm/


出力形式に注意。
符号だとか、0の場合だとかをきちんと処理するのが面倒。こういうのさくっとできるようになりたい。

ソースコード
int main()
{
	P p[3];
	while(cin>>p[0].real()>>p[0].imag())
	{
		rep(i,2)cin>>p[i+1].real()>>p[i+1].imag();
		
		P C=three_point_circle(p[0],p[1],p[2]);
		double c,d,e,r; r=abs(p[0]-C);
		
		if(abs(C.real())<EPS)printf("x");
		else printf("(x %c %.3f)",C.real()>0?'-':'+',abs(C.real()));
		printf("^2 + ");
		if(abs(C.imag())<EPS)printf("y");
		else printf("(y %c %.3f)",C.imag()>0?'-':'+',abs(C.imag()));
		printf("^2 = %.3f^2\n",r);
		
		c=2*C.real(); d=2*C.imag();
		e=r*r-C.real()*C.real()-C.imag()*C.imag();
		
		printf("x^2 + y^2");
		if(abs(c)>EPS)printf(" %c %.3fx",c>0?'-':'+',abs(c));
		if(abs(d)>EPS)printf(" %c %.3fy",d>0?'-':'+',abs(d));
		if(abs(e)>EPS)printf(" %c %.3f",e>0?'-':'+',abs(e));
		printf(" = 0\n\n");
	}
	return 0;
}

1269 Intersecting Lines

問題概要

二本の直線がその通過点(x1,y1),(x2,y2),(x3,y3),(x4,y4)により与えられる。
これらの直線が

  • 交差するときはその交点を、
  • 一致するときは"LINE"を、
  • 共有点を持たないときは"NONE"を出力せよ。
解法

spaghetti sourceのライブラリを使用(http://www.prefield.com/algorithm/
毎度思うんだけど、貼り付けるのに時間かかりすぎるんだよなあ。
コンテスト用にうまく自分用にまとめておかないといけないんだけど面倒。。。


そもそもコンテストで幾何あんまり出ないしねえ。

ソースコード
int main()
{
	int cs; cin>>cs;
	puts("INTERSECTING LINES OUTPUT");
	while(cs--)
	{
		P p[4];
		rep(i,4)cin>>p[i].real()>>p[i].imag();
		L l1(p[0],p[1]),l2(p[2],p[3]);
		
		if(!intersectLL(l1,l2))puts("NONE");
		else {
			P crs=crosspoint(l1,l2);
			if(crs==P(INF,INF))puts("LINE");
			else printf("POINT %.2f %.2f\n",crs.real(),crs.imag());
		}
	}
	puts("END OF OUTPUT");
	return 0;
}

1152 An Easy Problem!

問題概要

与えられた数をN進数と見て、それがN-1で割り切れるようなNのうち、最小のものを求めよ。そのようなNが存在しない場合は"such number is impossible!"を出力せよ。

N≦62以下、かつ与えられるデータの大きさは32KB以下である。

解法

Nを2から62まで全部試す。


N-1で割った余りというのは各桁の和をN-1で割った余りに等しいので、和だけ保存しておくようにすると計算量、コード記述量が減る。(工夫は要らないみたいだけど)


UVaの問題が出典らしいのだけど、なんか物凄く陰険な入力がある模様。(http://www.algorithmist.com/index.php/UVa_10093

ソースコード
int n;
char in[35000];

int main()
{
	while(gets(in))
	{
		int mxdig=0,sum=0,d;
		for(n=0;in[n];n++)
		{
			if(isdigit(in[n]))d=in[n]-'0';
			else if(isupper(in[n]))d=in[n]-'A'+10;
			else if(islower(in[n]))d=in[n]-'a'+36;
			else continue;
			
			sum+=d;
			mxdig=max(mxdig,d);
		}
		int ans=max(2,mxdig+1);
		for(;ans<=62;ans++)if(sum%(ans-1)==0)break;
		
		if(ans<=62)printf("%d\n",ans);
		else puts("such number is impossible!");
	}
	return 0;
}

3660 Cow Contest

問題概要

n頭の、その中の二頭の牛の強さの関係がm個与えられる。
このとき、強さの順位が正確に定まる牛の数を求めよ。


n≦100,m≦4500とする。牛の強さの関係が矛盾することはないとしてよい。

解法

1094の類題。
同様に強さの関係を有向グラフにして、ワーシャルフロイドする。
順位が正確に定まる牛というのは、(自分より弱い牛)+(自分より強い牛)==n-1となることに同値である。

ソースコード
int n,m;
int d[100][100];

int main()
{
	scanf("%d%d",&n,&m);
	rep(i,n)rep(j,n)d[i][j]=1;
	rep(i,m)
	{
		int a,b; scanf("%d%d",&a,&b);
		d[a-1][b-1]=0;
	}
	rep(k,n)rep(i,n)rep(j,n)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
	
	int ans=0;
	rep(i,n)
	{
		int cnt=0;
		rep(j,n)cnt+=d[i][j]==0||d[j][i]==0;
		if(cnt==n-1)ans++;
	}
	printf("%d\n",ans);
	
	return 0;
}

1094 Sorting It All Out

問題概要

n個のアルファベットはある数をあらわす。
それらの大小関係の式m個が与えられるとき、

  • 大小関係が一意に定まる
  • 矛盾する
  • 定まらない

のどれかを判定せよ。

解法

問題の種類トポロジカルソートでいいのかなあ。
komiyamさんのブログを参考にさせていただいた。(http://d.hatena.ne.jp/komiyam/20100806/1281109085


d[i][j]はi<jなら0,未確定なら1のようなグラフとすれば、サイクルはd[i][i]が0かどうかで判定できる。
サイクルの検出は一回ごとにワーシャルフロイドする方法で間に合う。


最後にピリオドを忘れていてずっとWA出してたorz

ソースコード
const int MX=100000;

int n,m,a[MX],b[MX];
int d[26][26];

void update()
{
	rep(k,n)rep(i,n)rep(j,n)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
int main()
{
	while(scanf("%d%d",&n,&m),n||m)
	{
		rep(i,n)rep(j,n)d[i][j]=1;
		rep(i,m)
		{
			char x,y,z; scanf(" %c%c%c",&x,&z,&y);
			a[i]=x-'A'; b[i]=y-'A';
		}
		
		int ans=-1;
		rep(i,m)
		{
			d[a[i]][b[i]]=0; update();
			rep(j,n)if(d[j][j]==0)
			{
				printf("Inconsistency found after %d relations.\n",i+1);
				goto END;
			}
			int cnt=0; rep(j,n)rep(k,n)cnt+=1-d[j][k];
			if(cnt==n*(n-1)/2)
			{
				ans=i+1; break;
			}
		}
		if(ans!=-1)
		{
			printf("Sorted sequence determined after %d relations: ",ans);
			pi tmp[n];
			rep(i,n)tmp[i]=mp(accumulate(d[i],d[i]+n,0),i);
			sort(tmp,tmp+n);
			rep(i,n)printf("%c",tmp[i].second+'A'); puts(".");
		}
		else puts("Sorted sequence cannot be determined.");
		END:;
	}
	return 0;
}

2785 4 Values whose Sum is 0

問題概要

四つの集合A,B,C,Dが与えられる。それぞれの要素数はn(n≦4000)である。
このときa∈A,b∈B,c∈C,d∈Dなる(a,b,c,d)で、a+b+c+d=0を満たすものの数を答えよ。


各要素の絶対値は2^28を超えないものとする。

解法

(a+b)としてできる値を全てMapに記憶して、c+dとしてできる値と、条件を満たすものをそれぞれ掛け合わせればよい。
STLのMapを使うと遅いので、hashを使う。


(本当はJavaのhashMapを使おうと思ったのだが、手元にJavaを書ける環境がないので、laycurse先生のhashを真似して、自前のhashを作った)

ソースコード
int n,a[4][4000];
const int hashMAX=9999991;
int hashk[hashMAX],hashv[hashMAX];

int hashFunc(ui k)
{
	return k*155707%hashMAX;
}
int hashGet(ui k)
{
	int i=hashFunc(k);
	for(;;)
	{
		if(hashk[i]==k&&hashv[i])break;
		if(!hashv[i])break;
		i++; if(i==hashMAX)i=0;
	}
	if(hashk[i]!=k)return 0;
	return hashv[i];
}
void hashSet(ui k,int v)
{
	int i=hashFunc(k);
	for(;;)
	{
		if(hashk[i]==k&&hashv[i])break;
		if(!hashv[i])break;
		i++; if(i==hashMAX)i=0;
	}
	hashk[i]=k; hashv[i]=v;
}
void hashInc(ui k)
{
	int i=hashFunc(k);
	for(;;)
	{
		if(hashk[i]==k&&hashv[i])break;
		if(!hashv[i])break;
		i++; if(i==hashMAX)i=0;
	}
	hashk[i]=k; hashv[i]++;
}

int main()
{
	scanf("%d",&n);
	rep(i,n)rep(j,4)scanf("%d",a[j]+i);
	
	int z=0;
	rep(i,n)rep(j,n)
	{
		int t=-a[0][i]-a[1][j];
		if(t)hashInc(t);
		else z++;
	}
	
	ll ans=0;
	rep(i,n)rep(j,n)
	{
		int t=a[2][i]+a[3][j];
		if(t)ans+=hashGet(t);
		else ans+=z;
	}
	printf("%lld\n",ans);
	
	return 0;
}