PKU演習問メモ(9/4)

か、解法は後で書くんだからねっ！

No.	問題名	問題の種類および解法	難易度
1659	Frogs' Neighborhood	探索	★★★★☆
1635	Subway tree systems	木の同型性判定・構文解析	★★★★☆
1679	The Unique MST	最小全域木	★★☆☆☆
1654	Area	多角形の面積	★★☆☆☆

1659 Frogs' Neighborhood

問題概要

n個の湖があり、それぞれが水路でつながっていたりいなかったりする。
各湖から、水路でつながっている湖の数が与えられるとき、それを満たす湖のつながりかたが存在する場合"YES"を出力し、その後湖のつながり方を表す隣接行列を出力せよ。
条件を満たすようなつながり方がない場合"NO"を出力せよ。

答えが複数ある場合どれを出力してもかまわない。
n≦20を満たす。

解法

単なる深さ優先探索で解ける。コードが長くなったので難易度むずかしめにしておいた。
候補の数が残り少ないところから埋めるようにしたが（コンビネーションを計算してほげほげしてる辺り）、別に工夫は要らないような気もした。

ソースコード

int C[20][20];
int n,a[10],con[10][10];

int BIT(int b)
{
	int ret=0;
	for(;b;b&=b-1)ret++;
	return ret;
}
bool sol()
{
	int mnc=inf,mni=0,mny;
	rep(i,n)
	{
		int x=0,y=0,tmp;
		rep(j,n)
		{
			if(con[i][j]==-1)x++;
			else if(con[i][j]==1)y++;
		}
		if(x==0)
		{
			if(y!=a[i])return 0;
			continue;
		}
		tmp=C[x][a[i]-y];
		if(tmp<mnc)mnc=tmp,mni=i,mny=y;
	}
	if(mnc==inf)return 1;
	
	int cand=0;
	rep(i,n)if(con[mni][i]==-1)cand|=1<<i;
	
	if(a[mni]==mny)
	{
		rep(i,n)if(cand&1<<i)con[mni][i]=con[i][mni]=0;
		if(sol())return 1;
		rep(i,n)if(cand&1<<i)con[mni][i]=con[i][mni]=-1;
		return 0;
	}
	for(int bit=cand;bit;bit=(bit-1)&cand)if(BIT(bit)==a[mni]-mny)
	{
		rep(i,n)if(cand&1<<i)con[mni][i]=con[i][mni]=(bit&1<<i)>0;
		if(sol())return 1;
		rep(i,n)if(cand&1<<i)con[mni][i]=con[i][mni]=-1;
	}
	return 0;
}
int main()
{
	rep(i,20)rep(j,i+1)C[i][j]=i==0||j==0||i==j?1:C[i-1][j]+C[i-1][j-1];
	
	int cs; scanf("%d",&cs);
	while(cs--)
	{
		scanf("%d",&n);
		rep(i,n)scanf("%d",a+i);
		rep(i,n)rep(j,n)con[i][j]=i==j?0:-1;
		
		if(sol())
		{
			puts("YES");
			rep(i,n)rep(j,n)printf("%d%c",con[i][j],j==n-1?'\n':' ');
		}
		else puts("NO");
		puts("");
	}
	return 0;
}

1635 Subway tree systems

問題概要

ツリー状になっている地下鉄がある。（中心となる駅があり、任意の二つの駅には必ずかつ一意な路が存在する）
その地下鉄を、根からスタートし、深さ優先探索で全てのノード辿り、根へ戻る。
このとき、根→葉の向きの辺を通るときに0,葉→根の向きの辺を通るときに1を出力すると、0と1からなる文字列が得られる。

このような二つの文字列が与えられたとき、その二つの文字列が同じ地下鉄を探索したものでありえるならば"same"を、ありえないならば"different"を出力せよ。
文字数は3000を超えない。

解法

spaghetti source木の同型性判定（http://www.prefield.com/algorithm/graph/tree_isomorphism.html）のコードを使用

一応自分でもグラフを子の要素の多い順に並べかえてけばいいじゃんとか思ったんだけど、stringをO(N^2)とかやったらTLEだろうなあとか思って云々。
結局グラフ作る部分でO(n^2)ではあるんだけどさ。

ソースコード

char in[3001];
Node* make(int s,int t)
{
	Node* ret=new Node;
	if(s>=t)return ret;
	
	int d=0,p=s;
	for(;s<t;s++)
	{
		if(in[s]=='1')d++;
		else d--;
		if(d==0)
		{
			ret->child.pb(make(p+1,s));
			p=s+1;
		}
	}
	return ret;
}

int main()
{
	int cs; scanf("%d",&cs);
	while(cs--)
	{
		Node *t1,*t2;
		scanf("%s",in); t1=make(0,strlen(in));
		scanf("%s",in); t2=make(0,strlen(in));
		
		puts(utreeIsomorphism(t1,t2)?"same":"different");
		delete(t1); delete(t2);
	}
	return 0;
}

1679 The Unique MST

問題概要

Minimum spanning tree（最小全域木）とは、あるグラフの部分グラフで木であるようなもののうち、辺の重みの和がそのようなグラフの中で最小のもののことを言う。
グラフが与えられたとき、そのMSTが一意に定まるならその辺の重みの和を、定まらないのなら"Not Unique!"を出力せよ。

解法

クソ問。

3 2
1 2 1
1 3 1

のMSTを"Not Unique!"と出力するプログラムを要求されてるなんて普通の人には読み取れませんよね。。。

とりあえずDisscussで言及されてたプリム法っぽいものをやったら通った。

ソースコード

int n,m;
vector<vector<pi> >e;
bool v[100];

int main()
{
	int cs; scanf("%d",&cs);
	while(cs--)
	{
		scanf("%d%d",&n,&m);
		e.clear(); e.resize(n);
		rep(i,m)
		{
			int a,b,c; scanf("%d%d%d",&a,&b,&c); a--; b--;
			e[a].pb(mp(c,b)); e[b].pb(mp(c,a));
		}
		rep(i,n)v[i]=0; v[0]=1;
		int ans=0;
		rep(it,n-1)
		{
			int mn=inf-1,mn2=inf,mni;
			rep(i,n)if(v[i])fr(j,e[i])if(!v[j->second])
			{
				if(j->first<=mn)mn2=mn,mn=j->first,mni=j->second;
			}
			if(mn==mn2)
			{
				ans=inf; break;
			}
			ans+=mn; v[mni]=1;
		}
		END:
		if(ans==inf)puts("Not Unique!");
		else printf("%d\n",ans);
	}
	return 0;
}

1654 Area

問題概要

座標平面上の格子点を原点から、周囲8方向に何回か移動する。
移動は数字の列によって表わされる。（格ゲーのレバー入力を表す方式で）
（東西南北の4方向は距離1,斜め移動は√2移動する。）

このとき、移動によって囲まれた面積を求めよ。

解法

多角形の面積を求める定石を使えばよい。

ソースコード

char in[1000001];

int crs(int x,int y,int a,int b)
{
	return x*b-a*y;
}
int main()
{
	int cs; scanf("%d",&cs);
	while(cs--)
	{
		scanf("%s",in);
		ll ans=0; int x=0,y=0,nx,ny;
		for(int i=0;in[i];i++)
		{
			if(in[i]=='7'||in[i]=='4'||in[i]=='1')nx=x-1;
			if(in[i]=='9'||in[i]=='6'||in[i]=='3')nx=x+1;
			if(in[i]=='1'||in[i]=='2'||in[i]=='3')ny=y-1;
			if(in[i]=='7'||in[i]=='8'||in[i]=='9')ny=y+1;
			if(in[i]=='5')nx=ny=0;
			
			ans+=crs(x,y,nx,ny);
			y=ny; x=nx;
		}
		if(ans<0)ans=-ans;;
		printf("%lld",ans/2);
		puts(ans%2?".5":"");
	}
	return 0;
}