PKU演習問メモ(8/24)

センスなくて死にたい。

No.	問題名	問題の種類および解法	難易度
2259	Team Queue	データ構造（キュー）	★★★☆☆
2258	The Settlers of Catan	グラフ・深さ優先探索	★★☆☆☆
2230	Watchcow	グラフ・深さ優先探索	★★★☆☆
2208	Pyramids	幾何・四面体の体積	★★★☆☆
2121	Inglish-Number Translator	実装・文字列	★★★☆☆

2259 Team Queue

問題概要

"Team Queue"を以下のようなキューとして定義する。

push

同じチームのデータがキューに入っているときはそれらの直後に、そうでない場合は最後尾にデータを追加する。

pop

先頭からデータを取り出す。

このとき、与えられたクエリを処理せよ。
チーム数は1000以下、クエリの数は200000以下である。

解法

クエリの数が大きく、O(1)でpop,pushの操作ができないといけない（と問題文にある）
チームの数が少ないので、チーム数分キューを作り、チーム全体を要素にする親玉のキューを作れる。
これにより各操作がO(1)で行える。

ソースコード

int team[1000000];

int main()
{
	int n,cs=0;
	while(scanf("%d",&n),n)
	{
		printf("Scenario #%d\n",++cs);
		rep(i,n)
		{
			int m,k; scanf("%d",&m);
			rep(j,m)scanf("%d",&k),team[k]=i;
		}
		vector<queue<int> > Q(n);
		queue<int> QQ;
		
		char op[10]; int t,tt;
		while(scanf("%s",op),op[0]!='S')
		{
			if(op[0]=='D')
			{
				tt=QQ.front(); t=Q[tt].front(); Q[tt].pop();
				printf("%d\n",t);
				if(Q[tt].empty())QQ.pop();
				
				continue;
			}
			scanf("%d",&t);
			tt=team[t];
			if(Q[tt].empty())QQ.push(tt);
			Q[tt].push(t);
		}
		puts("");
	}
	return 0;
}

2258 The Settlers of Catan

問題概要

"カタンの開拓者たち"のゲームにおける道の長さを求めよ。
（道の長さはカタンにおける定義にしたがう）
ゲームの状態は、都市の数n個および、m本のそれらを結ぶ道の情報により与えられる。
各都市の次数は3以下である。

また、n,m≦25を満たす。

解法

mが少ないので、使ったエッジにフラグを立てながら深さ優先で全探索すればよい。

ソースコード

int n,m;
pi e[60];
int top[60],rv[60],ans;
bool v[60];

void dfs(int c,int p,int s)
{
	ans=max(ans,s);
	for(int i=top[c];i;i=e[i].second)if(!v[i]&&p!=e[i].first)
	{
		v[i]=1; v[rv[i]]=1;
		dfs(e[i].first,c,s+1);
		v[i]=0; v[rv[i]]=0;
	}
}
int main()
{
	while(scanf("%d%d",&n,&m),n)
	{
		rep(i,60)e[i]=mp(0,0);
		rep(i,60)v[i]=top[i]=0;
		
		int ei=0;
		rep(i,m)
		{
			int a,b,t; scanf("%d%d",&a,&b);
			t=top[a]; top[a]=++ei; e[ei]=mp(b,t);
			t=top[b]; top[b]=++ei; e[ei]=mp(a,t);
			
			rv[ei-1]=ei; rv[ei]=ei-1;
		}
		ans=0;
		rep(i,n)
		{
			rep(j,n)v[j]=0; dfs(i,i,0);
		}
		printf("%d\n",ans);
	}
	return 0;
}

2230 Watchcow

問題概要

N個の牧場をM本の双方向に通行可能な道路が結んでいる。
今、1番の牧場を出発し、全ての道路を"違う向きに丁度1度ずつ（合計丁度2回）"通り、1番の道路に戻ってきたい。

そのようなルートを一つ出力せよ。
N≦10000,M≦50000を満たす。

解法

1番のノードから、一度使った辺は二度通らないように深さ優先探索をする。
行き止まりまで行ったら、自分を出力して、再帰関数は呼び出し元へと帰るが、そこで更にそのノードを出力する（更にその呼び出し元で……）とすると、丁度問題文で求められている経路を出力することができる。

辺のリストは以前に使った下のようなデータ構造が適しているように思われる。
（疎なグラフを省メモリに表すことができ、逆辺がO(1)で探せる）

ソースコード

int n,m;
struct S{
	int t,id;
};
S node[10001];
pi e[100001]; int rv[100001];
bool v[100000];
int ans[200000],l;

void dfs(int c,int p)
{
	ans[l++]=c;
	for(int ei=node[c].id;ei;ei=e[ei].second)
	if(e[ei].first!=p)
	{
		if(!v[ei])
		{
			v[ei]=1; v[rv[ei]]=1;
			dfs(e[ei].first,c);
			ans[l++]=c; 
		}
	}
	if(ans[l-1]!=c)ans[l++]=c; 
}

int main()
{
	scanf("%d%d",&n,&m);
	int ei=0;
	rep(i,m)
	{
		int a,b,tmp; scanf("%d%d",&a,&b);
		tmp=node[a].id;
		node[a].id=++ei; e[ei]=mp(b,tmp);
		rv[ei]=ei+1;
		
		tmp=node[b].id;
		node[b].id=++ei; e[ei]=mp(a,tmp);
		rv[ei]=ei-1;
	}
	dfs(1,1);
	rep(i,l)printf("%d\n",ans[i]);
	
	return 0;
}

2208

問題概要

四面体ABCDの四辺AB,AC,AD,BC,BD,CDの長さが与えられる。
このとき、四面体の体積を求めよ。

解法

辺の長さから四面体の体積を求める公式があるらしい。（５次の行列式を使うので手計算には向かない）
http://www004.upp.so-net.ne.jp/s_honma/figure/tetrahedronvolume.htm

ソースコード

spaghetti source行列式のコードを使用（http://www.prefield.com/algorithm/math/matrix.html）

int main()
{
	int a,b,c,p,q,r;
	scanf("%d%d%d%d%d%d",&a,&b,&c,&p,&q,&r);
	
	matrix M(5,array(5));
	rep(i,4)M[4][i]=M[i][4]=1;
	M[0][1]=M[1][0]=p*p; M[0][2]=M[2][0]=q*q; M[1][2]=M[2][1]=r*r;
	M[3][0]=M[0][3]=a*a; M[3][1]=M[1][3]=b*b; M[3][2]=M[2][3]=c*c;
	
	double ans=sqrt(det(M)/288);
	printf("%.4f\n",ans);
	
	return 0;
}

2121 Inglish-Number Translator

問題概要

"Inglish-Number"を数字に変換せよ。
（英語の数詞を使った数の表記だが、hundred,thousand,millionの前のoneが省略されない）

解法

構文解析に近いようなこと（もっと簡単）をする。
oneがあるので楽。ソース参照。

ソースコード

char* s1[]={"zero","one","two","three","four","five","six","seven","eight","nine","ten","eleven",
	"twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen","nineteen","twenty"};
char* s2[]={"thirty","forty","fifty","sixty","seventy","eighty","ninety","hundred"};

map<string,int> conv;
vs num;

int main()
{
	rep(i,21)conv[s1[i]]=i;
	rep(i,8)conv[s2[i]]=(i+3)*10;
	
	conv["negative"]=-1;
	conv["thousand"]=1000; conv["million"]=1000000;
	
	string in;
	while(getline(cin,in),in!="")
	{
		num.clear();
		stringstream ss(in);
		
		while(ss>>in)num.pb(in);
		
		int ans=0,tmp=0,sgn=1;
		fr(i,num)
		{
			if(conv[*i]==100)tmp*=100;
			else if(conv[*i]>100)ans+=tmp*conv[*i],tmp=0;
			else
			{
				if(conv[*i]<0)sgn=-1;
				else tmp+=conv[*i];
			}
		}
		ans+=tmp;
		
		cout<<ans*sgn<<endl;
	}
	return 0;
}