PKU演習問メモ(8/27) - simezi

No.	問題名	問題の種類および解法	難易度
2553	The Bottom of a Graph	強連結成分分解	★★★☆☆
2437	Muddy roads	貪欲法	★★☆☆☆
2457	Part Acquisition	幅優先探索・経路出力	★★★☆☆
2451	Uyuw's Concert	幾何・多角形の切断	★★★☆☆
2491	Scavenger Hunt	グラフ理論	★★☆☆☆
2484	A Funny Game	ゲーム	★★★☆☆

2553 The Bottom of a Graph

問題概要

有向グラフにおいて、ある頂点uから出発してたどり着ける全ての頂点vについて、v→uへの道があるような頂点uを"Bottom"と呼ぶことにする。
与えられたグラフの"Bottom"を全て出力せよ。

与えられるグラフの頂点の数は5000以下である。

解法

頂点uが"Bottom"であるとき、uの強連結成分は全て"Bottom"である。
強連結成分分解後にできる森のグラフにおいて"Bottom"は葉のノードであるため、
葉のノード（を構成する連結成分の頂点）を全て出力すればよい。

ソースコード

int main()
{
	int v,e;
	while(scanf("%d",&v),v)
	{
		scanf("%d",&e);
		Graph g(v);
		rep(i,e)
		{
			int a,b; scanf("%d%d",&a,&b); a--; b--;
			g[a].pb(Edge(a,b,1)); 
		}
		vector<vi> scc;
		stronglyConnectedComponents(g,scc);
		
		int p[5001];
		rep(i,v)p[i]=i;
		fr(i,scc)
		{
			int r=(*i)[0];
			fr(j,(*i))p[*j]=r;
		}
		vi ans;
		fr(i,scc)
		{
			fr(j,(*i))fr(k,g[*j])
			if(p[k->dst]!=(*i)[0])goto SKIP;
			
			fr(j,(*i))ans.pb(*j);
			SKIP:;
		}
		sort(all(ans));
		fr(i,ans)printf("%d%c",*i+1,i==ans.end()-1?'\n':' ');
	}
	return 0;
}

2437 Muddy roads

問題概要

数直線上にN個の泥の区間がある。
泥の区間は始点siと終点eiにより与えられる。
この泥の区間を長さLの板で全て覆いたい。板同士は重なってもよく、板が泥のない区間へはみ出してもよいとするとき、必要な板の枚数を求めよ。

N≦10000を満たす。

解法

区間をソートして、貪欲に板を敷いていけばよい。
整数の切り上げに若干注意が必要。

ソースコード

int n,l;
pi mud[10000];

int main()
{
	scanf("%d%d",&n,&l);
	rep(i,n)
	{
		int a,b; scanf("%d%d",&a,&b);
		mud[i]=mp(a,b);
	}
	sort(mud,mud+n);
	
	int p=-1,ans=0;
	rep(i,n)
	{
		while(i<n&&mud[i].second<p)i++;
		if(i==n)break;
		p=max(p,mud[i].first);
		
		int k=(mud[i].second-p)/l+((mud[i].second-p)%l!=0);
		p+=k*l; ans+=k;
	}
	printf("%d\n",ans);
	
	return 0;
}

2457 Part Acquisition

問題概要

1番のアイテムを、（１対１の）物々交換を繰り返してK番のアイテムにしたい。
物々交換の可能なリストが与えられるとき、最小の交換回数でK番のアイテムを得るための交換の順序を出力せよ。
そのような手順が複数ある場合どれを出力してもよい。手順が存在しない場合は-1を出力せよ。

K≦1000を満たす。

解法

物々交換のリストは有向グラフとみることができ、問題文で求められているのは1番のノードからK番のノードまでの最短経路を出力することに相当する。
幅優先探索で経路を求め、バックトラックにより経路を出力する。

ソースコード

int n,k,node[1001],p[1001];
pi e[50000];

int main()
{
	scanf("%d%d",&n,&k);
	int ei=0,tmp;
	rep(i,n)
	{
		int a,b; scanf("%d%d",&a,&b);
		e[++ei]=mp(b,node[a]); node[a]=ei;
	}
	
	p[1]=1;
	queue<int> Q; Q.push(1);
	while(!Q.empty())
	{
		int c=Q.front(); Q.pop();
		if(c==k)break;
		
		for(int i=node[c];i;i=e[i].second)if(!p[e[i].first])
		{
			p[e[i].first]=c;
			Q.push(e[i].first);
		}
	}
	
	if(p[k]==0)
	{
		puts("-1"); return 0;
	}
	
	int ans[1001],l=0;
	for(int i=k;i!=1;i=p[i])ans[l++]=i;
	ans[l++]=1;
	
	printf("%d\n",l);
	rep(i,l)printf("%d\n",ans[l-1-i]);
	
	return 0;
}

2451 Uyuw's Concert

問題概要

4頂点の座標が(0,0),(10000,0),(10000,10000),(0,10000)であるような正方形の広場がある。
ここに線分で表されるベンチがいくつかある。線分は正方形の辺と辺を結ぶ。
これらのベンチのどこに座っても見えるようなステージを作りたい。
そのようなステージの最大の面積を求めよ。

解法

カーゴ・カルト。
（多角形の切断＋多角形の面積のライブラリ使用）

ソースコード

int main()
{
	int n; scanf("%d",&n);
	G g;
	g.pb(P(0,0)); g.pb(P(10000,0));
	g.pb(P(10000,10000)); g.pb(P(0,10000));
	rep(i,n)
	{
		double a,b,c,d;
		scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
		g=convex_cut(g,L(P(a,b),P(c,d)));
	}
	printf("%.1f\n",area2(g)/2);
	
	return 0;
}

2491 Scavenger Hunt

問題概要

S個の地点があり、S-1個の"地点の名前次の地点の名前"の関係が与えられる。
このとき、できるだけ長い地点の名前の列を作れ。

S≦333を満たす。

解法

関係を有向グラフと見ると、分岐のない木になる。
根からdfsすればよい。

ソースコード

struct S{
	char s[100];
	bool operator<(const S &r)const{
		return strcmp(s,r.s)<0;
	}
};
S pl[350];
int n,in[350];
bool e[350][350];

void dfs(int cur)
{
	puts(pl[cur].s);
	rep(i,n)if(e[cur][i])
	{
		dfs(i); break;
	}
}
int main()
{
	int CS; scanf("%d",&CS);
	rep(cs,CS)
	{
		scanf("%d",&n);
		rep(i,n)in[i]=0;
		rep(i,n)rep(j,n)e[i][j]=0;
		
		map<S,int> id; int nid=0;
		S t1,t2;
		rep(i,n-1)
		{
			scanf("%s%s",t1.s,t2.s);
			if(!id.count(t1))
			{
				pl[nid]=t1; id[t1]=nid++;
				
			}
			if(!id.count(t2))
			{
				pl[nid]=t2; id[t2]=nid++;
			}
			e[id[t1]][id[t2]]=1;
			in[id[t2]]++;
		}
		
		printf("Scenario #%d:\n",cs+1);
		rep(i,n)if(in[i]==0)
		{
			dfs(i); break;
		}
		puts("");
	}
	return 0;
}

2484 A Funny Game

問題概要

n枚のコインを円状に並べ、二人で次のようなゲームを行う。
連続する1枚または2枚のコインを取っていき、最後にコイン取ったプレイヤーが勝ちとなる。
お互いが最善を尽くすとするとき、ゲームの勝者を求めよ。

解法

コインが円形に並んでいる状態は考えにくいので、その次の状態から考える。
すると、山が1個ある石取りゲームのようになる。
プレイヤーは山から1個または2個石をとり、山を適当なところで分割させることもできる。

このときどのプレイヤーが勝つかというと、

先手必勝の山・後手必勝の山に分けられるとき→後手必勝の山でわざと負けて、先手番で先手必勝の山で勝てる
先手必勝の山二つに分けられるとき→負ける
後手必勝の山二つに分けられるとき→どっちかの山で好きに勝敗を決められるので勝てる

となるので、これをプログラムにして1000くらいまで実行させてみると、n≧3で常に後手必勝となることがわかる。

ソースコード

int main()
{
	int n;
	while(scanf("%d",&n),n)puts(n==1||n==2?"Alice":"Bob");
	return 0;
}
/*
bool ans[1000];
int main()
{
	ans[1]=ans[2]=1;
	for(int i=3;i<1000;i++)
	{
		for(int l=1;l<3;l++)rep(j,i-l+1)
		{
			int a=j,b=i-j-l+1;
			if(!ans[a]&&!ans[b])
			{
				ans[i]=1;
				goto NEXT;
			}
		}
		NEXT:;
	}
	
	int n;
	while(scanf("%d",&n),n)puts(n<3||!ans[n-1]||!ans[n-2]?"Alice":"Bob");
	return 0;
}
*/