PKU演習問メモ(6/11) - simezi

久しぶりすぎて表のフォーマット忘れた（ぁ

No.	問題名	問題の種類および解法	難易度
3047	Bovine Birthday	曜日計算	★☆☆☆☆
1188	Gleaming the Cubes	区間の交わり	★☆☆☆☆
2643	Election	シミュレーション	★☆☆☆☆
2263	Heavy Cargo	貪欲法	★☆☆☆☆
2624	4th Point	幾何	★☆☆☆☆

3047 Bovine Birthday

問題概要

与えられた年月日の曜日を求めよ。

解法

Zellerの公式を用いると楽。

ソースコード

int main()
{
	char day[][9]={"satur","sun","mon","tues","wednes","thurs","fri"};
	
	int y,m,d,j,k,h;
	cin>>y>>m>>d;
	
	if(m<3)m+=12,y--;
	j=y/100,k=y%100;
	
	h=(d+int((m+1)*2.6)+k+k/4+j/4+5*j)%7;
	cout<<day[h]<<"day"<<endl;
	
	return 0;
}

1188 Gleaming the Cubes

問題概要

n個の立方体について、角の座標(x[i],y[i],z[i])および一辺の長さa[i]が与えられる。
それぞれの立方体は、角の座標からx軸,y軸,z軸のそれぞれの正の方向に、座標軸に平行に辺が伸びている。
このときn個の立方体の交わりの体積を求めよ。

解法

区間[a1,b1]と[a2,b2]の交わりは[max(a1,a2),min(b1,b2)]である。この交わりを取る操作をx,y,zの各成分ごとに行っていけばよい。

ソースコード

int main()
{
	int n;
	while(cin>>n,n)
	{
		int M[3],m[3];
		rep(i,3)M[i]=inf,m[i]=-inf;
		
		rep(i,n)
		{
			int p[3],a;
			rep(j,3)cin>>p[j];
			cin>>a;
			
			rep(j,3)M[j]=min(M[j],p[j]+a),m[j]=max(m[j],p[j]);
		}
		
		int ans=1;
		rep(i,3)ans*=max(0,M[i]-m[i]);
		cout<<ans<<endl;
	}
	
	return 0;
}

2643 Election

問題概要

選挙の候補n人の、名前と所属政党が与えられる。
m票の投票が与えられたとき、当選者の所属政党を答えよ。

ただし、無効票はどの候補の票にもならず、結果が引き分けならば"tie"と出力せよ。

解法

mapで候補の番号を記憶しておくとよい。候補は20人なので線形探索でも余裕かな？
AC少ないからTLE厳しいのかと思ってchar[]でやったが単にWAが多いだけだった。
多分無効票の処理ではまった人が多いのだろう。

ソースコード

struct S{
	char str[81];
	bool operator<(const S &r)const
	{
		return strcmp(str,r.str)<0;
	}
};

int main()
{
	int n,m;
	char party[20][81];
	map<S,int> toi;
	
	scanf("%d ",&n);
	S tmp;
	rep(i,n)
	{
		gets(tmp.str); gets(party[i]);
		toi[tmp]=i;
	}
	
	scanf("%d ",&m);
	int vote[20]={0},winner=-1,mx,cnt=0;
	rep(i,m)
	{
		gets(tmp.str);
		if(toi.count(tmp))vote[toi[tmp]]++;
	}
	
	mx=*max_element(vote,vote+n);
	rep(i,n)if(vote[i]==mx)
	{
		winner=i; cnt++;
	}
	
	printf("%s\n",cnt==1?party[winner]:"tie");
	
	return 0;
}

2263 Heavy Cargo

問題概要

各都市と都市の間を結ぶ道路にはそれぞれ重量制限がある。
この制限を満たして、与えられたスタートの都市からゴールにたどり着く道のうち、最もゆるい重量制限の値を求めよ。

都市の数はn≦200,
道の本数はm≦19900を満たす。

解法

ダイクストラ法の要領で優先度付きキューを使い、ゴールに着くまで最も重量制限のゆるい通路を辿っていけばよい。
グラフには隣接行列を用いるのがよい。

ソースコード

int e[200][200];

int main()
{
	int n,m,cs=0;
	while(cin>>n>>m,n)
	{
		cout<<"Scenario #"<<++cs<<endl;
		
		rep(i,n)fill_n(e[i],n,0);
		
		int city=0;
		map<string,int> toi;
		rep(i,m)
		{
			int ia,ib,w;
			string a,b; cin>>a>>b>>w;
			if(!toi.count(a))toi[a]=city++;
			if(!toi.count(b))toi[b]=city++;
			
			ia=toi[a]; ib=toi[b];
			e[ia][ib]=e[ib][ia]=w;
		}
		string s,t; cin>>s>>t;
		int is=toi[s],it=toi[t];
		
		int mx[200]={0},ans=0; mx[is]=inf;
		priority_queue<pi> Q; Q.push(mp(inf,is));
		while(!Q.empty())
		{
			int c=Q.top().second,cw=Q.top().first; Q.pop();
			if(c==it)
			{
				ans=cw; break;
			}
			
			rep(i,n)
			{
				int nw=min(cw,e[c][i]);
				if(mx[i]>=nw)continue;
				mx[i]=nw;
				Q.push(mp(nw,i));
			}
		}
		cout<<ans<<" tons"<<endl<<endl;
	}
	
	return 0;
}

2624 4th Point

問題概要

平行四辺形の隣り合う2辺の両端の座標が与えられる。
このとき、残りの頂点の座標を求め、小数点以下3桁までの小数に丸めて出力せよ。

解法

まずは与えられた2辺が重なっている頂点を求める。
その頂点をP(p)とすればPに2本の辺のベクトルaとbを加算すれば求める頂点になる。

ソースコード

なんかセンスない実装すぎるなあ。

int main()
{
	P p[4],pp,ans;
	while(cin>>p[0].real()>>p[0].imag())
	{
		rep(i,3)cin>>p[i+1].real()>>p[i+1].imag();
		rep(i,4)rep(j,4)if(i!=j&&abs(p[i]-p[j])<EPS)
		{
			pp=p[i];
			break;
		}
		
		ans=pp;
		rep(i,2)
		{
			ans+=(abs(p[i*2]-pp)<EPS?p[i*2+1]:p[i*2])-pp;
		}
		
		printf("%.3f %.3f\n",ans.real(),ans.imag());
	}
	
	return 0;
}