PKU演習問メモ(8/28)

No.	問題名	問題の種類および解法	難易度
2565	Average is not Fast Enough!	実装	★☆☆☆☆
2570	Fiber Network	ワーシャルフロイド・ビット演算	★★★☆☆
2536	Gopher II	二部グラフの最大マッチング	★★☆☆☆
2501	Average Speed	実装	★★☆☆☆
2531	Network Saboteur	探索	★★☆☆☆
2513	Colored Sticks	一筆書き・Trie	★★★★☆
2528	Mayor's posters	座標圧縮	★★☆☆☆
1221	UNIMODAL PALINDROMIC DECOMPOSITIONS	動的計画法	★★☆☆☆

2565 Average is not Fast Enough!

問題概要

合計距離がdで、n区間のマラソンの、各区間の記録が与えられる。
このとき、1km走るのにかかった全体での平均の時間を求めよ。

ただし、一人でも失格者がいた場合、"-"を出力せよ。

解法

かかった時間を秒になおして合計して、距離を割る。
問題文では秒は切り上げにしろ、みたいなことが書いてあるが、四捨五入しないとサンプルすら通らない。謎。
どうみてもかかった時間の単位は秒なのにmin/kmを単位につけるのも謎。

ソースコード

int sec(char *s)
{
	if(s[0]=='-')return -1;
	
	int ret=0;
	ret+=3600*(s[0]-'0');
	ret+=60*((s[2]-'0')*10+s[3]-'0');
	ret+=(s[5]-'0')*10+s[6]-'0';
	return ret;
}
int main()
{
	int n; double d;
	scanf("%d%lf",&n,&d);
	
	int t; char tm[20][10];
	while(~scanf("%d",&t))
	{
		rep(i,n)scanf("%s",tm[i]);
		int sum=0;
		rep(i,n)
		{
			int a=sec(tm[i]);
			if(a<0)
			{
				sum=-1; break;
			}
			sum+=a;
		}
		printf("%3d: ",t);
		if(sum==-1)puts("-");
		else
		{
			sum=(int)(sum/d+0.5);
			printf("%d:%02d min/km\n",sum/60,sum%60);
		}
	}
	return 0;
}

2570 Fiber Network

問題概要

有向グラフであらわされるネットワークが与えられる。
辺についている文字（一文字の英小文字）は、どの企業がその辺を利用できるかである。
企業の文字と、二つの番号s,tが与えられたとき、その企業はs→tへの通信路をもっているかを判定せよ。

グラフの頂点の数は200以下である。

解法

文字は最大26であるので、i番目の企業が辺を利用できるかの情報をi番目のビットとしてもたせることができる。
すると、一度のワーシャルフロイドで全ての計算ができる。

printfの入力はまとめないとTLE.（putcharなら大丈夫なのかな？試してない）

ソースコード

int n,e[200][200];

int main()
{
	while(scanf("%d",&n),n)
	{
		rep(i,n)rep(j,n)e[i][j]=0;
		
		int a,b; char str[30];
		while(scanf("%d%d",&a,&b),a)
		{
			a--; b--; scanf("%s",str);
			for(int i=0;str[i];i++)e[a][b]|=1<<str[i]-'a';
		}
		rep(k,n)rep(i,n)rep(j,n)e[i][j]|=e[i][k]&e[k][j];
		while(scanf("%d%d",&a,&b),a)
		{
			a--; b--; int j=0;
			rep(i,26)if(e[a][b]&1<<i)str[j++]='a'+i;
			if(j==0)str[j++]='-'; str[j]=0;
			puts(str);
		}
		puts("");
	}
	return 0;
}

Gopher II

問題概要

n匹のリスとm個の穴がある。
それぞれの穴には最大1匹のリスが入ることができる。
各リスおよび穴の座標が与えられたとき、s秒以内で穴に入ることのできないリスの数を最小にしたい。
このような最小値を求めよ。
なお、リスの移動速度は等しくvである。

n,m,s,v≦100を満たす。

解法

リスと穴で二部グラフの最大マッチングをすればよい。
リスと穴は、そのリスがその穴にs秒以内で入ることができる場合に辺を貼る。

ソースコード

int n,m,s,v;
bool e[200][200];
int p[200]; bool vis[200];

bool match(int s)
{
	if(s<0)return 1;
	for(int i=s<n?n:0;i<(s<n?n+m:n);i++)if(!vis[i]&&e[s][i])
	{
		vis[i]=1;
		if(match(p[i]))return p[i]=s,p[s]=i,1;
	}
	return 0;
}
int main()
{
	while(~scanf("%d%d%d%d",&n,&m,&s,&v))
	{
		double x[200],y[200];
		rep(i,n+m)scanf("%lf%lf",x+i,y+i);
		rep(i,n)for(int j=n;j<n+m;j++)e[i][j]=e[j][i]=hypot(x[i]-x[j],y[i]-y[j])<=s*v;
		
		rep(i,n+m)p[i]=-1;
		int ans=n;
		rep(i,n)
		{
			rep(j,n+m)vis[j]=0;
			if(match(i))ans--;
		}
		printf("%d\n",ans);
	}
	return 0;
}

2501 Average Speed

問題概要

ドライブの記録が"時刻 変化後の時速"で与えられる。
時刻が与えられたとき、その時点での移動距離を求めるクエリを処理せよ。

時刻は全て昇順に並んでいるものとする。

解法

その時点までの移動距離を覚えながら、新しい移動距離を足し算していく。
入力ケースに速度が最初に入力されないものがある模様。微妙に悪問。

ソースコード

int calc(char *s)
{
	int ret=0;
	rep(i,3)
	{
		ret*=60;
		ret+=(s[i*3]-'0')*10+s[i*3+1]-'0';
	}
	return ret;
}
int main()
{
	double d=0;
	int s=0,t,prevt;
	
	char in[100],dmy[100];
	
	while(gets(in))
	{
		t=calc(in);
		d+=s*(t-prevt)/3600.0;
		prevt=t;
		
		if(in[8])sscanf(in,"%s%d",dmy,&s);
		else printf("%s %.2f km\n",in,d);
	}
	
	return 0;
}

2531 Network Saboteur

問題概要

n個のコンピュータからなるネットワークがある。
i番とj番のコンピュータの通信量はC[i][j](=C[j][i])である。

このとき、コンピュータを二つのグループにわけ、グループ間で行われている通信量を最大になるようにしたい。
そのようなときの通信量を求めよ。

n≦20を満たす。

解法

上手いやり方が思い浮かばなかったが、nが小さいので部分集合を全部列挙してみた。
これ通るんだ。。。

ソースコード

int n,f[20][20];

int main()
{
	scanf("%d",&n);
	rep(i,n)rep(j,n)scanf("%d",f[i]+j);
	
	int ans=0;
	rep(i,1<<n-1)
	{
		int flow=0,bit=i|1<<n-1;
		rep(j,n)if(1<<j&bit)rep(k,n)if(!(1<<k&bit))
		flow+=f[j][k];
		ans=max(ans,flow);
	}
	printf("%d\n",ans);
	
	return 0;
}

2513 Colored Sticks

問題概要

両端に色のついた棒がある。
同じ色をした端同士をつなげて一本の長い棒をつくりたい。

それぞれの棒の、それぞれの端の色が10字以下の文字列として与えられるとき、一本の棒にできるかどうかを判定せよ。

解法

MLEにTLEにWAを計18回出した。すんごい苦労した。
まあTrieの使い方解ったからいいかあ。

にしても連結性チェックにUnion-Find使うとACでDFS使うとWAってのは謎。

一本の長い棒を作れるかは、棒の端を頂点、棒を辺としたグラフを考えれば、そのグラフが一筆書き可能かどうかに帰着する。

グラフが一筆書き可能かどうかは、"連結かつ、次数奇数の頂点が0個または2個である"に必要十分。
ゆえにその判定をUnion-Findと、色ごとの出現回数を数えることで行ってやればよい。

色ごとの出現回数を数えるには、mapやhashを使う必要がありそうだが、
STLのmapを使うと、（stringを使わないでも）TLE.
Trieというデータ構造を使うとmapよりも高速に同じことができる。

ソースコード

struct Trie {
  int value;
  Trie *next[26];
  Trie() { value=0; fill(next, next+26, (Trie*)0); }
};
Trie *find(char *t, Trie *r) {
  for (int i = 0; t[i]; ++i) {
    int c = t[i]-'a';
    if (!r->next[c]) r->next[c] = new Trie;
    r = r->next[c];
  }
  return r;
}

int p[500000];
int root(int x)
{
	if(x==p[x])return x;
	return p[x]=root(p[x]);
}

int n;
bool deg[500000];

int main()
{
	rep(i,500000)p[i]=i;
	
	Trie trie;
	char s1[11],s2[11];
	
	int ei=0,a,b,t;
	while(~scanf("%s%s",s1,s2))
	{
		Trie *t1=find(s1,&trie),*t2=find(s2,&trie);
		if(!t1->value)t1->value=++n;
		if(!t2->value)t2->value=++n;
		
		a=t1->value-1,b=t2->value-1;
		deg[a]^=1; deg[b]^=1; //mod2
		
		a=root(a); b=root(b);
		if(a!=b)p[b]=a;
	}
	
	int odd=0;
	rep(i,n)
	{
		if(deg[i])odd++;
		if(odd>2)break;
	}
	if(odd==0||odd==2)
	{
		int r=root(0);
		rep(i,n)if(root(i)!=r)goto FAIL;
		
		puts("Possible"); return 0;
	}
	FAIL:
	puts("Impossible");
	
	return 0;
}

2528 Mayor's posters

問題概要

長さが10000000の壁にn枚のポスターが貼られる。
ポスターは、"候補 左端の座標 右端の座標"の形式で与えられ、与えられた順番に貼られ、同じ座標にすでにポスターが貼られていた場合は上から下にあるものが隠れる。

全てのポスターを貼り終えたあと、見えるポスターの枚数を求めよ。
n≦10000を満たす。

解法

座標は10000000までと値が大きいが、全て整数であるので、座標圧縮できる。
すると普通に区間を塗りつぶす問題にできる。

ソースコード

int n,l[10000],r[10000],v[20000];
int w[20000]; bool ok[10000];

int main()
{
	int cs; scanf("%d",&cs);
	while(cs--)
	{
		scanf("%d",&n);
		rep(i,n)scanf("%d%d",l+i,r+i),v[i*2]=l[i],v[i*2+1]=r[i];
		
		sort(v,v+2*n);
		int m=unique(v,v+2*n)-v;
		rep(i,n)l[i]=lower_bound(v,v+m,l[i])-v,r[i]=lower_bound(v,v+m,r[i])-v;
		
		rep(i,2*n)w[i]=-1; rep(i,n)ok[i]=0;
		rep(i,n)for(int j=l[i];j<=r[i];j++)w[j]=i;
		int ans=0;
		rep(i,2*n)if(w[i]>=0&&!ok[w[i]])ans++,ok[w[i]]=1;
		printf("%d\n",ans);
	}
	return 0;
}

1221 UNIMODAL PALINDROMIC DECOMPOSITIONS

問題概要

Unimodal Palindromic Decompositionsとは、左右対称な自然数からなる数列で、左半分は単調非減少かつ、右半分は単調非増加なものをいう。
項の和がNであるようなUPDの数を求めよ。

解法

Nの範囲が書いてないくせに、long longを使わないとWAになるというちょい悪問……

動的計画法により解くことができる。
dp[i][j]に和の残りがiで、最後の項がjである作りかけのUPDの場合の数を持たせる。

ソースコード

int n;
ll dp[300][300];

int main()
{
	while(scanf("%d",&n),n)
	{
		rep(i,n+1)rep(j,n+1)dp[i][j]=0;
		for(int i=1;i<=n;i++)dp[n-i][i]=1;
		for(int i=1;i*2<=n;i++)dp[n-2*i][i]=1;
		
		for(int r=n;r>0;r--)for(int i=1;i<=n;i++)if(dp[r][i])
		for(int j=1;j<=i&&r-2*j>=0;j++)dp[r-2*j][j]+=dp[r][i];
		
		ll ans=0;
		rep(i,n+1)ans+=dp[0][i];
		cout<<n<<" "<<ans<<endl;
	}
	return 0;
}