PKU演習問メモ(9/13) 700問達成!!!

PKU

さてさて。。。最近ペースが落ちすぎてるので、本も届いたことだしペースを取り戻したい。
それから、解説も後回しになったり、適当になったりしているので、丁寧にやる。
（解説読んだけど解らなかったとか言われないようにしたいorz）

No. 問題名 問題の種類および解法 難易度
3536 Beer Refrigerator 素因数分解 ★★★☆☆
2872 Spelling Be データ構造（Trie） ★★★☆☆
2935 Basic Wall Maze 幅優先探索・経路出力 ★★★☆☆
2961 Sylvester construction フラクタル ★★★☆☆
2976 Dropping tests 貪欲法 ★★★★☆
2493 Rdeaalbe 実装 ★★☆☆☆

これで累計700問!!!

3536 Beer Refrigerator

問題概要

1x1x1の箱がn個ある。
これらがぴったり入るような、各辺の長さが整数の直方体の冷蔵庫を作りたい。
ただし、冷蔵庫は冷気漏れを最小限にするため、表面積を最小にしなければならない。


そのような冷蔵庫の一辺の長さ（直方体の辺3つ）をスペースで区切り出力せよ。
n≦10^6を満たす。

解法

直方体の辺をx,y,z(x≦y≦z)とする。
xの長さとしてありえるのは、x*x*x≦nまで。nは小さいので順に割れるものから候補として試してよい。(10^6に対して最大100個しかxの候補はない）


xの候補を決めた後、x≦y≦zを満たすようなyの候補をそれぞれ試す。
これも制限よりy*y≦nで、どんなに多くてもせいぜい1000個しかないので、全て割って試してよい。

ソースコード
int n,a,b,c,s;

void calc(int yz,int x)
{
	for(int y=x;y*y<=yz;y++)if(yz%y==0)
	{
		int ss=x*y+yz+yz/y*x;
		if(ss<s)a=x,b=y,c=yz/y;
	}
}
int main()
{
	scanf("%d",&n);
	s=inf;
	for(int i=1;i*i*i<=n;i++)if(n%i==0)calc(n/i,i);
	printf("%d %d %d\n",a,b,c);
	
	return 0;
}

2872 Spelling Be

問題概要

n個の単語からなる辞書と、m通のE-mailが与えられる。
辞書によりメールをスペルチェックしたい。


メールはいくつかの単語からなる。メール内に、辞書に存在しない単語がなければ、
"Email X is spelled correctly."を出力し、存在するなら
"Email X is not spelled correctly."を出力した後、辞書に存在しなかった単語を全て改行により区切って、順に出力せよ。辞書に存在しない同じ単語が2度以上出てきた場合も、それらをその回数だけ全て出力せよ。

解法

制約条件が書かれていないが、各単語を1000字以下、NGの単語を1000語以下にしたら通った。


辞書の中に単語が入っているか判定するだけだが、時間制限が若干厳しく、setなどを使うと（STLのstringを使わずとも）TLEになる。
データ構造としてTrieを使えば制限時間内に実行を終えることができる。


spaghetti sourceのTrie（http://www.prefield.com/algorithm/string/trie.html）のコードを使用。

ソースコード
char in[1000],ng[1000][1000];

int main()
{
	int m,n;
	while(~scanf("%d ",&m))
	{
		Trie *trie=new Trie();
		rep(i,m)
		{
			gets(in);
			Trie *t=find(in,trie); t->value=1;
		}
		scanf("%d ",&n);
		rep(i,n)
		{
			int sz=0;
			while(gets(in),strcmp(in,"-1"))
			{
				Trie *t=find(in,trie);
				if(t->value==1)continue;
				strcpy(ng[sz++],in);
			}
			if(sz==0)
			{
				printf("Email %d is spelled correctly.\n",i+1); continue;
			}
			printf("Email %d is not spelled correctly.\n",i+1);
			rep(j,sz)puts(ng[j]);
		}
		delete trie;
	}
	puts("End of Output");
	return 0;
}

2935 Basic Wall Maze

問題概要
  • 6x6マスからなり、
  • 壁が3枚内部にあり、
  • スタートとゴールがそれぞれ一ヶ所存在する

ような迷路が与えられる。
この迷路のスタートからゴールまで最短距離で辿り着くような、経路を(NWSEからなる文字列として）出力せよ。
そのような経路が複数ある場合、どれを出力してもかまわない。


移動は、東西南北に（一辺を共有して）隣接し、なおかつその間に壁が存在しないようなグリッドにのみ移動できるものとする。

解法

null文字忘れてWAくらうとか集中力不足。。。
座標を二倍する解法もあるが、経路出力と微妙に相性が悪いような気もする。


縦の壁と横の壁をそれぞれboolで持っておくとよい。

ソースコード
int dy[]={-1,0,1,0},dx[]={0,-1,0,1};
int p[7][7];
bool tate[7][7],yoko[7][7];

int main()
{
	char *dir="NWSE";
	
	int sy,sx,gy,gx;
	while(scanf("%d%d",&sx,&sy),sx)
	{
		scanf("%d%d",&gx,&gy);
		rep(i,7)rep(j,7)tate[i][j]=yoko[i][j]=0,p[i][j]=-1;
		
		rep(i,3)
		{
			int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d);
			if(a==c)
			{
				if(b>d)swap(b,d);
				for(int y=b;y<d;y++)tate[y+1][a]=1;
			}
			else
			{
				if(a>c)swap(a,c);
				for(int x=a;x<c;x++)yoko[b][x+1]=1;
			}
		}
		queue<pi> Q; Q.push(mp(sy,sx));
		while(!Q.empty())
		{
			int y=Q.front().first,x=Q.front().second; Q.pop();
			rep(d,4)
			{
				int ny=y+dy[d],nx=x+dx[d];
				if(ny<=0||nx<=0||ny>6||nx>6||p[ny][nx]>=0)continue;
				if(d==0&&yoko[y-1][x]||d==2&&yoko[y][x]||
d==1&&tate[y][x-1]||d==3&&tate[y][x])continue;
				p[ny][nx]=d; Q.push(mp(ny,nx));
				if(ny==gy&&nx==gx)goto END;
			}
		}
		END:;
		char ans[100]; int l=0;
		for(int y=gy,x=gx;y!=sy||x!=sx;)
		{
			int d=p[y][x],ny=y-dy[d],nx=x-dx[d];
			ans[l++]=dir[d];
			y=ny; x=nx;
		}
		reverse(ans,ans+l); ans[l]=0;
		puts(ans);
	}
	return 0;
}

2961 Sylvester construction

問題概要

Hadamard matrix(アダマール行列)とは、各要素が1または-1であり、Hn*tHn=nInを満たすような行列を言い、具体的には
H1=(1)
H2n=( (Hn Hn),(Hn -Hn) )
のように表される。


今、n,x,y,w,hが与えられたときHnのx行y列からはじまり、高さh,幅wの部分行列を出力せよ。
n≦2^62かつnは2の累乗であり、x,y,w,hは行列の内部に収まる範囲であるとしてよい。
w,h≦20を満たす。

解法

Hnのi行j列目を出力するような関数を考える。
これは、フラクタルを出力する要領で、再帰を繰り返すことで求めることができる。
再帰の回数はlog_2 n回である。


w,hはともに20以下と小さいので、この関数をw*h回呼び出して部分行列を求めればよい。

ソースコード
int rec(ll n,int y,int x)
{
	if(n==1)return 1;
	ll m=n/2;
	if(y>=m&&x>=m)return -rec(m,y-m,x-m);
	return rec(m,y<m?y:y-m,x<m?x:x-m);
}
int main()
{
	int cs; scanf("%d",&cs);
	while(cs--)
	{
		ll n; int x,y,w,h;
		scanf("%lld%d%d%d%d",&n,&x,&y,&w,&h);
		rep(i,h)rep(j,w)printf("%d%c",rec(n,y+i,x+j),j==w-1?'\n':' ');
		puts("");
	}
	return 0;
}

2976 Dropping tests

問題概要

n個のテストがあり、それぞれの満点はa[i]点、自分の得点はb[i]点であった。
これらのうちk個を除外した、残りのテストにおける以下の値を最大にしたい。
(Σa[i])/(Σb[i])


n,k,a[i],b[i]が与えられたとき、この値の最大値を求めよ。

解法

サンプルを見て判る通り、a[i]/b[i]が最も高いものを貪欲にn-k個選んでも、それが最適解にならない場合がある。


証明ができなかったのだが、以下のような貪欲法をしたら通った。酷い。
（だ、誰か証明教えて……）


現在の(Σa[i])/(Σb[i])に、そのテストをつけ加えた時の値の減少量が最も少ないものを順に足していく。

ソースコード
int n,k,a[1000],b[1000];
bool use[1000];

int main()
{
	while(scanf("%d%d",&n,&k),n)
	{
		rep(i,n)scanf("%d",a+i),use[i]=0;
		rep(i,n)scanf("%d",b+i);
		
		double mx=0; int mi=0;
		rep(i,n)if(1.0*a[i]/b[i]>mx)mx=1.0*a[i]/b[i],mi=i;
		use[mi]=1;
		
		ll x=a[mi],y=b[mi];
		rep(i,n-k-1)
		{
			mx=0; int mj=0;
			rep(j,n)if(!use[j]&&1.0*(x+a[j])/(y+b[j])>mx)
			mx=1.0*(x+a[j])/(y+b[j]),mj=j;
			
			use[mj]=1; x+=a[mj]; y+=b[mj];
		}
		printf("%d\n",(int)(100.0*x/y+0.5));
	}
	return 0;
}

2493 Rdeaalbe

問題概要

人間の情報処理の研究によると、英単語は、先頭と末尾の文字以外は、その順序を好き入れ替えても認識することができるという。


単語n個からなる辞書と、いくつかの単語からなる文が与えられる。
この文の単語は、先頭と末尾の文字以外は、その順序を入れ替えられているかもしれない。
このような文を、与えられた辞書の単語から作る作り方は何通りあるか求めよ。

解法

n文字の2つの単語が、先頭と末尾以外の文字を並べ替えて相互に変換可能であるかは、
2文字目〜n-1文字目の部分をソートして、ソート後で単語が一致するかどうかを見ることで判定可能である。


文の各単語が、辞書のどの単語に相当しうるかを上のような考え方で調べ、場合の数を掛け算していく。
辞書内で相互に変換可能な単語がある場合があるので、それは最初に纏めておくと計算量が節約できる。

ソースコード
struct S{
	char s[101];
	bool operator<(const S &r)const{
		return strcmp(s,r.s)<0;
	}
};
int m,n;
char in[10001];

int main()
{
	int CS; scanf("%d",&CS);
	rep(cs,CS)
	{
		scanf("%d",&n);
		map<S,int> M;
		S tmp;
		rep(i,n)
		{
			scanf("%s",tmp.s);
			int l=strlen(tmp.s);
			if(l>3)sort(tmp.s+1,tmp.s+l-1);
			M[tmp]++;
		}
		scanf("%d ",&m);
		printf("Scenario #%d:\n",cs+1);
		
		rep(i,m)
		{
			gets(in);
			stringstream ss(in);
			string str;
			ll ans=1;
			while(ss>>str)
			{
				strcpy(tmp.s,str.c_str());
				int l=strlen(tmp.s);
				if(l>3)sort(tmp.s+1,tmp.s+l-1);
				ans*=M[tmp];
			}
			printf("%lld\n",ans);
		}
		puts("");
	}
	return 0;
}