PKU演習問メモ(8/23)

PKU

問題解けないorzorz
解法書く時間ないorzorz←あとでかく←書いた

No. 問題名 問題の種類および解法 難易度
2138 Travel Games 深さ優先探索 ★★★☆☆
2160 Box 実装 ★☆☆☆☆
2226 Muddy Fields 二部グラフの最小点被覆 ★★★★★
2239 Selecting Courses 二部グラフの最大マッチング ★★★★☆
2271 HTML 実装・文字列 ★★☆☆☆

2138 Travel Games

問題概要

D単語からなる辞書が与えられる。
辞書の中の3文字の単語から出発して、その文字の好きな場所（先頭または末尾も含む）に一文字アルファベットを加え、別の辞書に載っている単語を作る、という操作を繰り返す。


辞書および出発する単語が与えられたとき、この操作によって得られる最も長い単語を求めよ。
D≦1000,各単語の文字数は80以下を満たす。

解法

ある単語からある単語が作れるかどうかグラフを作り、深さ優先探索で根から最も遠いノードを求めればよい。単なる木の探索。

ソースコード
struct S{
	int len;
	char s[81];
	bool operator<(const S &r)const{
		return len<r.len;
	}
};
S s[1000];
bool v[1000],e[1000][1000];
int n; char str[81];

int dfs(int c)
{
	v[c]=1;
	int i=c; while(i<n&&s[i].len==s[c].len)i++;
	
	int mxi=c,mxlen=s[c].len;
	for(;i<n&&s[i].len==s[c].len+1;i++)if(e[c][i]&&!v[i])
	{
		int t=dfs(i);
		if(mxlen<s[t].len)mxlen=s[t].len,mxi=t;
	}
	return mxi;
}
bool ok(int a,int b)
{
	int i=0,j=0;
	for(;i<s[a].len&&j<s[b].len;i++,j++)if(s[a].s[i]!=s[b].s[j])i--;
	return i==s[a].len;
}

int main()
{
	scanf("%d%s",&n,str);
	rep(i,n)scanf("%s",s[i].s),s[i].len=strlen(s[i].s);
	sort(s,s+n);
	
	rep(i,n)
	{
		int j=i+1; while(j<n&&s[j].len==s[i].len)j++;
		for(;j<n&&s[j].len==s[i].len+1;j++)
		if(ok(i,j))e[i][j]=1;
	}
	
	int ans;
	rep(i,n)if(strcmp(str,s[i].s)==0)
	{
		ans=dfs(i); break;
	}
	puts(s[ans].s);
	
	return 0;
}

2160 Box

問題概要

6枚の長方形の板の辺の長さがそれぞれ与えられる。
このとき、この6枚の板を使い直方体が作れるかどうか判定せよ。

解法

まず、合同な3組の板が必要なので、それがあるかどうかを調べる。
次に、辺の長さの種類が3種類以下かどうかを調べる。

ソースコード
int main()
{
	int a[6],b[6];
	set<int> S;
	rep(i,6)
	{
		scanf("%d%d",a+i,b+i);
		S.insert(a[i]); S.insert(b[i]);
		if(a[i]>b[i])swap(a[i],b[i]);
	}
	bool u[6]={0};
	rep(i,6)if(!u[i])
	{
		for(int j=i+1;j<6;j++)if(!u[j])
		if(a[i]==a[j]&&b[i]==b[j])
		{
			u[i]=u[j]=1; break;
		}
	}
	int cnt=0;
	rep(i,6)cnt+=u[i];
	if(cnt!=6||S.size()>3)puts("IMPOSSIBLE");
	else puts("POSSIBLE");
	
	return 0;
}

2226 Muddy Fields

問題概要

hxwのグリッドにいくつか泥のマスがある。幅1で好きな長さの板を使い、次の条件を満たすようこの泥のマスを覆いたい。

  • 泥のマスは全て板により覆われる
  • 板同士は重なってもよい
  • 板が泥のないマスにはみでてはいけない

このとき、必要な板の枚数を求めよ。

解法

まずは縦および横の板の候補を、長さをできるだけ長くして、全て敷くことにする。
そして、左側を縦の板、右側を横の板にし、板同士が交わる場合そこに辺を引くような二部グラフを考える。


すると、板同士の交わりは泥のマスをあらわすことになり、またそのマスは最低でも縦の板または横の板のどちらかひとつにより覆われなければならない。
これは二部グラフの最小辺カバーに相当する。


最小辺カバーは最大マッチングの個数に等しいため、最大マッチングを求めればよい。

ソースコード
struct BD{
	int y,x,len;
	BD(int y=0,int x=0,int len=0):y(y),x(x),len(len){}
};
BD tate[1250],yoko[1250];
int nt,ny;

int h,w;
char fd[50][51];

int p[2500];
bool v[2500],e[2500][2500];

bool crs(int y,int t)
{
	int x1=yoko[y].x,x2=yoko[y].x+yoko[y].len-1;
	int y1=tate[t].y,y2=tate[t].y+tate[t].len-1;
	
	return (y1<=yoko[y].y&&yoko[y].y<=y2&&
		x1<=tate[t].x&&tate[t].x<=x2);
}
bool match(int s)
{
	if(s<0)return 1;
	for(int i=(s<ny?ny:0);i<(s<ny?ny+nt:ny);i++)
	if(e[s][i]&&!v[i])
	{
		v[i]=1;
		if(match(p[i])) return p[i]=s,p[s]=i,1;
	}
	return 0;
}

int main()
{
	scanf("%d%d",&h,&w);
	rep(i,h)scanf("%s",fd[i]);
	
	rep(i,h)
	{
		int p=-1;
		rep(j,w+1)
		{
			if(j==w||fd[i][j]=='.')
			{
				if(p!=-1)yoko[ny++]=BD(i,p,j-p),p=-1;
			}
			else if(p==-1)p=j;
		}
	}
	rep(j,w)
	{
		int p=-1;
		rep(i,h+1)
		{
			if(i==h||fd[i][j]=='.')
			{
				if(p!=-1)tate[nt++]=BD(p,j,i-p),p=-1;
			}
			else if(p==-1)p=i;
		}
	}
	rep(i,ny)rep(j,nt)if(crs(i,j))e[i][j+ny]=e[j+ny][i]=1;
	rep(i,ny+nt)p[i]=-1;
	
	int ans=0;
	rep(i,ny)
	{
		rep(j,ny+nt)v[j]=0;
		if(match(i))ans++;
	}
	printf("%d\n",ans);
	
	return 0;
}

2239 Selecting Courses

問題概要

Li Mingの通う大学には7日間、一日に12コマの授業がある。
それぞれのコマで開講される講義のカリキュラムが与えられる。
ひとつの講義は、一週間に複数回全く同じ講義が行われる場合があり、それらは、そのうちどれかひとつしか履修することができない。


Li Mingが一週間で履修できる最大の講義の数を求めよ。

解法

週84コマで、授業がn個あるとnx84のテーブルができる。
このテーブルから授業を、各列からひとつ、各行からひとつ選ぶような選び方が、条件を満たす講義の選び方である。
そのうち数が最大のものを求めればよい。


したがって二部グラフの最大マッチングを使うことができる。
すなわち、左側に84個のノード、右側にn個のノードを置き、授業がある場合辺を引く。
同じコマに取れる授業（つまり、左側のノードから出てる辺のうち選べるのは1つだけ）の制限と、同じ授業のうちとれるのはひとつだけの制限（左と同様）を考えればそのグラフのそれが最大マッチングであることは容易にわかる。


きづかなかったけど。

ソースコード
int n;
bool e[384][384];
int p[384];
bool v[384];

bool match(int s)
{
	if(s<0)return 1;
	for(int i=s<300?300:0;i<(s<300?384:n);i++)
	if(e[s][i]&&!v[i])
	{
		v[i]=1;
		if(match(p[i]))return p[s]=i,p[i]=s,1;
	}
	return 0;
}

int main()
{
	while(~scanf("%d",&n))
	{
		rep(i,384)rep(j,384)e[i][j]=0;
		rep(i,n)
		{
			int t,p,q; scanf("%d",&t);
			rep(j,t)scanf("%d%d",&p,&q),e[i][p*12+q-13+300]=e[p*12+q-13+300][i]=1;
		}
		rep(i,384)p[i]=-1;
		
		int ans=0;
		rep(i,300)
		{
			rep(j,384)v[j]=0;
			if(match(i))ans++;
		}
		printf("%d\n",ans);
	}
	return 0;
}

2271 HTML

問題概要

<hr> <br>を整形する簡易HTMLを作りたい。
以下のルールに従い、複数行からなる入力を整形して表示せよ。

  • 一行の字数は80字
  • 単語間の複数の空白または改行は1つの空白に置き換わる
  • 次の単語を表示すると80字を超える場合、その単語は次の行の先頭から表示する
  • <hr>は、現在の位置が行頭でなければ改行し、80個の"-"を表示する
解法

与えられた条件に従い実装する。ソースコード参照。

ソースコード
int main()
{
	string hr;
	rep(i,80)hr.pb('-');
	
	vector<string> vs;
	string str,in;
	while(getline(cin,str))
	{
		str.pb(' '); vs.pb(str); 
	}
	in=accumulate(all(vs),string());
	
	stringstream ss(in);
	int p=0;
	while(ss>>str)
	{
		if(str=="<br>")cout<<endl,p=0;
		else if(str=="<hr>")
		{
			if(p!=0)cout<<endl;
			cout<<hr<<endl; p=0;
		}
		else
		{
			if(p!=0)cout<<' ',p++;
			if(p+str.size()>80)cout<<endl,p=0;
			
			cout<<str; p+=str.size();
		}
	}
	cout<<endl;
	
	return 0;
}