PKU演習問メモ(9/6)

PKU

問題を解くのが遅すぎて解説を書く時間および気力ががが

No. 問題名 問題の種類および解法 難易度
3439 Server Relocation 幅優先探索 ★★★☆☆
1493 Machined Surfaces 実装 ★☆☆☆☆
1563 The Snail 実装 ★★☆☆☆
1509 Glass Beads Suffix array ★★★★☆
1502 MPI Maelstrom ワーシャルフロイド ★★☆☆☆
1521 Entropy ハフマン符号 ★★★★☆

3439 Server Relocation

問題概要

コンピュータの電源コードをsのコンセントからtのコンセントへつなぎ変えたい。
このコンピュータには二本の電源コードがあり、そのどちらかを常にコンセントにつなぎ、停電しないようにしなければならない。

電源コードの長さl1,l2,各コンセントの座標が与えられたとき、条件を満たす移動で、コンセントを挿す最小の回数のものの、回数を求めよ。

解法

コードの長さl1+l2の範囲でコンピュータが移動できると考える。
そうすると普通の幅優先探索で解ける。


が、やたらタイムリミットが厳しい。（気がする）
浮動小数点の比較がコストとしてきいてくるとは……

ソースコード
int n,X[1000],Y[1000];
bool con[1000][1000];
bool v[1000];

int main()
{
	int cs; scanf("%d",&cs);
	while(cs--)
	{
		int s,t; double l,l2;
		scanf("%d%d%d%lf%lf",&n,&s,&t,&l,&l2);
		s--; t--; l+=l2; l*=l;
		
		rep(i,n)scanf("%d%d",X+i,Y+i);
		rep(i,n)rep(j,i)con[i][j]=con[j][i]=
		l>=1.0*(X[i]-X[j])*(X[i]-X[j])+1.0*(Y[i]-Y[j])*(Y[i]-Y[j]);
		
		rep(i,n)v[i]=0; v[s]=1;
		queue<pi> Q; Q.push(mp(0,s));
		while(!Q.empty())
		{
			int c=Q.front().second,cc=Q.front().first; Q.pop();
			
			if(c==t)
			{
				printf("%d\n",cc); goto END;
			}
			rep(i,n)if(!v[i]&&con[c][i])v[i]=1,Q.push(mp(cc+1,i));
		}
		puts("Impossible"); END:;
	}
	return 0;
}

1493 Machined Surfaces

問題概要

ギザギザの板が二つある。左側の表面を横から見た図および、右側の表面を横から見た図があたえられる。
これらを水平に平行移動してくっつける。
（最も距離の短い部分がぴたりと接し、それより短いところには隙間ができる）


このときできる隙間の数をもとめよ。（隙間は半角スペース1個分につき一つと数える）

解法

(元々の隙間)-(移動距離)*(行数)=(隙間)
により求められる。
移動距離は最も短い部分の距離。

ソースコード
int n;
char in[26];

int main()
{
	while(scanf("%d ",&n),n)
	{
		int mn=inf,sp=0;
		rep(i,n)
		{
			gets(in);
			int j=0,cnt=0;
			rep(j,25)if(in[j]==' ')cnt++;
			mn=min(cnt,mn); sp+=cnt;
		}
		sp-=mn*n;
		printf("%d\n",sp);
	}
	return 0;
}

1563 The Snail

問題概要

なめくじが深さHの井戸の底にいる。毎日、昼の間Uにだけ壁を登り、夜の間にDだけ壁を落ちる。が、二日目以降は疲れるので壁を登る距離はF%だけ減少する。（元のUに対する比率で）
このとき、なめくじが井戸の外に出られるかどうかと、出られる場合その日数を、出られない場合は井戸の底へ再び落ちて戻ってくる日数を答えよ。


なめくじは負の高さは登らないものとする。また、各入力は100以下の自然数である。

解法

井戸の外へ出るあるいは井戸の底につくは、不等式で等号が入らないことに注意。
日数も距離も小さいので、毎日昼と夜をシミュレートする解法で間に合う。

ソースコード
int h,u,d,f;

int main()
{
	while(scanf("%d%d%d%d",&h,&u,&d,&f),h)
	{
		int n=1;
		double c=0,dist=u;
		for(;;n++)
		{
			c+=max(0.0,dist); if(c>h)break;
			c-=d; if(c<0)break;
			dist-=u*f/100.0;
		}
		printf("%s on day %d\n",c>h?"success":"failure",n);
	}
	return 0;
}

1509 Glass Beads

問題概要

英小文字からなる文字列であらわされるビーズが並んだネックレスがある。
この両端は繋がっている。
ネックレスの"最も弱い部分"を、ネックレスをその文字で切ったときの文字列が最小になるような文字の番号とする。

与えられた入力に対しネックレスの最も弱い部分を求めよ。それが複数ある場合最も番号の小さいものを出力せよ。
入力は10000文字以下である。

解法

カーゴカルト再び。


なんとなくSuffix Arrayを使えばよい気がしたのでspaghetti sourceのコードを使って書いてみた。ら通った。

与えられた文字列を二回繰り返した文字列のSAを作る。
それで元の文字列以下のインデックスで、最初に出てくるのが答え。
文字列の最後は、'z'+1の番兵にしておいたらなんか上手くいった（酷

ソースコード
char in[20001];

int main()
{
	int cs; scanf("%d",&cs);
	while(cs--)
	{
		scanf("%s",in);
		int n=strlen(in);
		rep(i,n)in[i+n]=in[i];
		in[2*n-1]='z'+1; in[2*n]=0;
		
		int *sa=buildSA(in,2*n);
		rep(i,2*n)if(sa[i]<n)
		{
			printf("%d\n",sa[i]+1); break;
		}
		delete(sa);
	}
	return 0;
}

1502 MPI Maelstrom

問題概要

プロセッサがn個あり、1番から全てに指令を出す。
各プロセッサの通信にかかる時間の行列があたえられるとき、全てのプロセッサに指令が届くのにかかる時間を求めよ。


A→Bの通信およびB→Aの通信にかかる時間は等しいため、行列は下三角行列で与えられる。また、行列の成分がxであるのは、そのプロセッサ間で直接通信ができないことを意味する。


n≦100を満たす。

解法

行列を隣接行列とみて、1番のノードから最も遠いノードの距離を求めると、それが答え。（微妙に英語の問題文と合わないような気がするのだけど）


ダイクストラ法orワーシャルフロイド法など。
nが小さいのでワーシャルフロイドしても間に合う。こっちのほうが楽。

ソースコード
int n,d[100][100];
char in[100];

int main()
{
	scanf("%d",&n);
	rep(i,n)rep(j,i)
	{
		scanf("%s",in);
		if(!isdigit(in[0]))
		{
			d[i][j]=d[j][i]=inf; continue;
		}
		for(int k=0;in[k];k++)d[i][j]*=10,d[i][j]+=in[k]-'0';
		d[j][i]=d[i][j];
	}
	rep(k,n)rep(i,n)rep(j,n)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
	
	printf("%d\n",*max_element(d[0],d[0]+n));
	
	return 0;
}

1521 Entropy

問題概要

与えられた英大文字またはアンダースコアからなる文字列をハフマン符号でエンコードし、元の長さとエンコード後の長さ、およびそれらの比率を出力せよ。


ハフマン符号は以下のような性質を満たす

  • 各文字に一つの二進数を割り当てる
  • いかなる文字を表す二進数も、他のいかなる文字を表す二進数の接頭辞になっていない
  • かつエンコード後の全体の長さが最小になる
解法

これはハフマン木の作り方を知らないと解けない問題（な気がする）
ぐーぐる先生によると以下のようにすればよいらしい。

  • 出現頻度が最も低い順にアルファベット二つに0,1の符号を割り当てる
  • 上の二つのアルファベットを一つのアルファベットとし、残りアルファベットから出現頻度が低い順にアルファベット二つに0,1の符号を割り当てる
  • すでにその文字に符号が割り当てられていた場合、先頭にその0または1をくっつける
  • これをアルファベットが一文字になるまで繰り返す


らしい。priority_queueとビット演算を使って適当に実装したのが以下。
どうやるのが楽なんだろ。

ソースコード
int l;
char in[100000];

int main()
{
	while(scanf("%s",in),strcmp(in,"END"))
	{
		l=strlen(in); sort(in,in+l);
		
		int dist[30]={0},n=-1;
		rep(i,l)
		{
			if(i==0||in[i]!=in[i-1])n++;
			dist[n]++;
		}
		n++;
		sort(dist,dist+n);
		
		int codelen[30]; rep(i,30)codelen[i]=0;
		priority_queue<pi> Q;
		rep(i,n)Q.push(mp(-dist[i],1<<i));
		while(!Q.empty())
		{
			int b=Q.top().second,d=-Q.top().first; Q.pop();
			if(Q.empty())break;
			int b2=Q.top().second,d2=-Q.top().first; Q.pop();
			b^=b2; d+=d2;
			rep(i,n)if(b&1<<i)codelen[i]++;
			if(Q.empty())break;
			Q.push(mp(-d,b));
		}
		int ans=0;
		rep(i,n)ans+=max(1,codelen[i])*dist[i];
		printf("%d %d %.1f\n",l*8,ans,l*8.0/ans);
	}
	return 0;
}