PKU演習問メモ(8/6)

なんとか問題演習を軌道にのせたい。今のしょぼしょぼペースだと目標をまともに達成できない。

No.	問題名	問題の種類および解法	難易度
1948	Triangular Pastures	動的計画法	★★★★☆
1745	Divisibility	動的計画法	★★☆☆☆
1141	Brackets Sequence	動的計画法・バックトラック	★★★☆☆
2677	Tour	動的計画法	★★★★☆
3171	Cleaning Shifts	動的計画法	★★★☆☆
3140	Contestants Division	木DP（メモ化再帰）・木のデータ構造	★★★★☆
3211	Washing Clothes	動的計画法	★★☆☆☆

1948 Triangular Pastures

問題概要

n本のフェンスを全て使って、三角形をつくる。できる三角形の最大の面積を求めよ。
n≦40かつ、
各フェンスの長さL[i]は整数で、かつL[i]≦40を満たす。

三角形が作れない場合は-1を出力せよ。

解法

自力で解けなかったので解説探してきた。DPニガテ！！

dp[i][j]に二つの辺の長さがi,jの三角形が作れるかを持っておく。
この表を、フェンスを0番から順に使って更新していけば、全ての作れる三角形が
O(ns^2)の計算量で求められる。

全てのフェンスの長さの合計をsとすると、
三角不等式からa+b＜cよりc＜s/2がいえる。
ので、全ての辺はs/2より短い。よって表にはs/2までを持っておけば十分である。

頭いいなあ。

ソースコード

int n,a[40];
bool dp[801][801];

int area(int a,int b,int c)
{
	if(abs(a-b)>=c||c>=a+b)return -1;
	
	double s=(a+b+c)/2.0;
	return (int)(sqrt(s*(s-a)*(s-b)*(s-c))*100);
}

int main()
{
	scanf("%d",&n);
	int sum=0,half;
	rep(i,n)scanf("%d",a+i),sum+=a[i];
	half=sum/2;
	
	rep(i,half+1)rep(j,half+1)dp[i][j]=0;
	dp[0][0]=1;
	
	rep(i,n)for(int j=half;j>=0;j--)for(int k=j;k>=0;k--)
	if(j>=a[i]&&dp[j-a[i]][k]||k>=a[i]&&dp[j][k-a[i]])
		dp[j][k]=1;
	
	int ans=-1;
	rep(i,half+1)rep(j,i+1)if(dp[i][j])
		ans=max(ans,area(i,j,sum-i-j));
	printf("%d\n",ans);
	
	return 0;
}

1745 Divisibility

問題概要

n個数字が与えられる。これらの数字を、順番を変えずそれらの間に+,-を任意の挿入して式を作る。（ただし先頭に-をつけることはできない）

このとき、値がkの倍数になる式を作ることができるかどうかを判定せよ。
n≦10000, k≦100を満たす。

解法

式の作り方は2^(n-1)通りあるが、kの倍数か判定するだけなので、kで割った余りだけを考えればよい。
すると計算量O(nk)のDPができる。
dp[i][j]に、i番目までの項を使ってjの値を作れるかどうかのbool値を持っておいて、テーブルを順次更新していく。

ソースコード

int n,k,num[10000];
bool dp[2][101];

int main()
{
	scanf("%d%d",&n,&k);
	rep(i,n)
	{
		int t; scanf("%d",&t);
		num[i]=(t%k+k)%k;
	}
	
	rep(i,k+1)dp[0][i]=0;
	dp[0][num[0]]=1;
	
	int cur=0,next=1;
	for(int i=1;i<n;i++)
	{
		rep(j,k+1)dp[next][j]=0;
		rep(j,k+1)if(dp[cur][j])dp[next][(j+num[i])%k]=dp[next][(j+k-num[i])%k]=1;
		
		swap(cur,next);
	}
	puts(dp[cur][0]?"Divisible":"Not divisible");
	
	return 0;
}

1141 Brackets Sequence

問題概要

"regular brakets"とは、括弧の対応が正しい文字列をいう。

(), [], (()), ()[], ()[()]は"regular brakets"であるが、
(, ], )(, ([)], ([(]はそうではない。

100文字以下の'(',')','[',']'からなる文字列が与えられた時、
この文字列を部分文字列として含む、（連続する部分とは限らない）最短の"regular brakets"を求めよ。
それが複数ある場合どれを出力してもかまわない。

解法

2955 Bracketsとほぼ同一の問題。
2955のように、最長のregularな部分文字列を見つけた後で、そこに使われず余った括弧について、隣に対応する括弧を補完してやったものが答えとなる。

したがって、そのコード（http://d.hatena.ne.jp/simezi_tan/20100627/1277600915）がほぼ流用できる。
使われずに余った文字を求めるには、一度DPをした後で、最適解となっている部分だけ再帰を辿ればよい（バックトラック）

ソースコード

int len;
string str;
int dp[101][101];
bool use[101];

int rec(int s,int t)
{
	if(s>=t)return 0;
	int &ret=dp[s][t];
	if(ret>=0)return ret;
	ret=0;
	for(;s<t;s++)for(int i=s;i<t;i++)
	if(str[s]=='('&&str[i]==')'||str[s]=='['&&str[i]==']')
		ret=max(ret,2+rec(s+1,i)+rec(i+1,t));
	
	return ret;
}
void rec2(int s,int t)
{
	int opt=dp[s][t];
	
	for(;s<t;s++)for(int i=s;i<t;i++)
	if(str[s]=='('&&str[i]==')'||str[s]=='['&&str[i]==']')
	if(2+rec(s+1,i)+rec(i+1,t)==opt)
	{
		use[s]=use[i]=1;
		rec2(s+1,i); rec2(i+1,t);
		return;
	}
}

int main()
{
	cin>>str; len=str.size();
	rep(i,len+1)rep(j,len+1)dp[i][j]=-1;
	rec(0,len);
	
	fill_n(use,len,0); rec2(0,len);
	
	string ans;
	rep(i,len)if(use[i])ans.pb(str[i]);
	else
	{
		if(str[i]=='('||str[i]==')')ans.pb('('),ans.pb(')');
		else ans.pb('['),ans.pb(']');
	}
	cout<<ans<<endl;
	
	return 0;
}

2677 Tour

問題概要

平面上のn個の点が与えられる。
それぞれの座標を(x[i],y[i])とすると、x[0]＜x[1]＜……＜x[n-1]を満たす。
x[0]から出発し、途中でいくつか点を通りながらx[n-1]まで移動して、x[n-1]から先ほど通っていなかった点を通ってx[0]まで戻る。

往路は通る点のx座標は常に大きくなるよう、復路では通る点のx座標は常に小さくなるよう点を選び、往路と復路で全ての点を通らなければならない。

このような移動のなかで、最小の移動距離を求めよ。

解法

nの大きさに関する条件が問題文中で与えられていなかったが、適当に3000を上限にしたら通った。
往路と復路の両方の最適解をx[0]から動的計画法により求める。
（2本の線分をx[0]から伸ばしていく）

ソースコード

const int MX=3000;
int n,X[MX],Y[MX];
double d[MX][MX],dp[MX][MX];

int main()
{
	while(~scanf("%d",&n))
	{
		rep(i,n)scanf("%d%d",X+i,Y+i);
		if(n==1)printf("%.2f\n",0);
		
		rep(i,n)rep(j,n)
		{
			d[i][j]=hypot(X[i]-X[j],Y[i]-Y[j]);
			dp[i][j]=INF;
		}
		
		dp[1][0]=d[1][0];
		for(int i=1;i<n-1;i++)rep(j,i)
		{
			dp[i+1][i]=min(dp[i+1][i],dp[i][j]+d[j][i+1]);
			dp[i+1][j]=min(dp[i+1][j],dp[i][j]+d[i][i+1]);
		}
		double ans=INF;
		rep(i,n)ans=min(ans,dp[n-1][i]+d[n-1][i]);
		printf("%.2f\n",ans);
	}
	return 0;
}

3171 Cleaning Shifts

問題概要

N頭の牛は、それぞれt1[i]からt2[i]までの時間、S[i]の給料で働く。
今、MからEまでの時間を常に少なくとも一頭の牛が掃除をしている状態にしたい。
（ただし、MからEまでの時間には、両端を含む。すなわち、E-M+1秒間を意味する）

このために必要な費用の最小値を求めよ。
N≦10000,
0≦M≦t1[i],t2[i]≦E≦86399を満たす。

解法

TLEが多いので時間が厳しいのかと思ったら別にそんなことは（ｒｙ

牛をt1が小さい順に並べ、dpの表を更新していけばよい。表の更新は単純に塗りつぶす方式で間に合った。
（上手くやると二分探索とか出来るのだろうか。よくわからない）

[追記]
id:nodchip:20100705の日記にnodchipさんが詳しいコードを載せていたので、そちらのほうが計算量的に優れた解法。やっぱり二分探索をするようだ。

ソースコード

struct S{
	int t1,t2,s;
	bool operator<(const S &r)const{
		return t1<r.t1;
	}
};
int n,m,e;
S cow[10000];
ll dp[86400];

void nul(int t,ll v)
{
	while(t>=0&&dp[t]>v)dp[t--]=v;
}

int main()
{
	scanf("%d%d%d",&n,&m,&e);
	e-=m;
	rep(i,n)
	{
		int a,b;
		scanf("%d%d%d",&a,&b,&cow[i].s);
		cow[i].t1=a-m; cow[i].t2=b-m;
	}
	sort(cow,cow+n);
	fill_n(dp,e+1,inf);
	
	int c=0;
	for(;c<n&&cow[c].t1<=0;c++)nul(cow[c].t2,cow[c].s);
	for(;c<n;c++)
	{
		if(dp[cow[c].t1-1]!=inf)nul(cow[c].t2,dp[cow[c].t1-1]+cow[c].s);
		else break;
	}
	
	printf("%lld\n",dp[e]==inf?-1:dp[e]);
	return 0;
}

3140 Contestants Division

問題概要

n個のノードからなる木が与えられる。
この木を二つに分けるような分割のうち、「それぞれのグループのノードに書かれた値の和」の差の絶対値が最小になるようなものを求めたい。このときの絶対値を求めよ。

解法

問題文が物凄く読みにくいので色々と検索してみたところ、与えられるグラフは木らしい。
で、普通にTree DPをすればいいかと思いきや、vector<vector<int> >を使うとTLE.枝刈りをしてもTLE.色々と酷い。
酷いけどPKUだとよくあること……

で、隣接リストを上手いこと使うと構造体の配列のみでグラフを表すデータ構造を作れるということもわかった。
以下のコードはそれのほぼ丸写し。（コーディングスタイルは自分のものに合わせたが）

ソースコード

const int MX=100001;

struct Node{
	int num,child; ll sum;
};

pi e[MX*2];//idx,next
Node node[MX];

int n,m;
ll ans,sum;

void rec(int c)
{
	node[c].sum=node[c].num;
	
	for(int next=node[c].child;next;next=e[next].second)
	{
		if(!node[e[next].first].sum)
		{
			rec(e[next].first);
			node[c].sum+=node[e[next].first].sum;
			ll t=sum-node[e[next].first].sum*2;
			if(t<0)t=-t;
			ans=min(ans,t);
		}
	}
}

int main()
{
	int cs=0;
	while(scanf("%d%d",&n,&m),n)
	{
		sum=0;
		rep(i,n)
		{
			scanf("%d",&node[i].num);
			sum+=node[i].num;
			node[i].sum=node[i].child=0;
		}
		int ei=0;//e[]の最後の要素
		rep(i,m)
		{
			int s,t,tmp; scanf("%d%d",&s,&t);
			s--; t--;
			tmp=node[s].child;
			node[s].child=++ei; e[ei]=mp(t,tmp);
			
			tmp=node[t].child;
			node[t].child=++ei; e[ei]=mp(s,tmp);
		}
		ans=1LL<<60; rec(0); 
		printf("Case %d: %lld\n",++cs,ans);
	}
	return 0;
}

3211 Washing Clothes

問題概要

m枚の洗濯物があり、それの色はn色のうちいずれかである。
この洗濯物を二人で洗濯するが、色移りを防ぐために、1つの色の洗濯を全て終えた後で別の色洗濯に取り掛かる。

二人で同時に1枚の洗濯物を洗うことはできず、別の洗濯物ならば同時に洗うことができる。
それぞれの洗濯物を洗うのにかかる時間が与えられたとき、全ての洗濯を終わらせるために必要な最短の時間を求めよ。
m＜100,n＜10,
1枚の洗濯にかかる時間は1000未満を満たす。

解法

問題文からはわかりにくいが、1色の洗濯が終わるまでは、もう一人も待機しなければならない。

すると、どの色の洗濯物を何番目に洗うかは関係ないことがわかる。
それぞれの色の洗濯物を洗い終えるのにかかる時間を単純に足せばよい。

その部分は典型的なナップサック問題であるので、動的計画法により求められる。

時間制限が厳しいのかと思ったけれど、まったく厳しくなかった。なぜこんなにTLEが出ているのか謎。

ソースコード

int n,m;
vector<vi> times;
bool dp[1000001];

int calc(int c)
{
	vi &time=times[c]; sort(all(time));
	int s=time.size(),sum=accumulate(all(time),0);
	
	fill_n(dp,sum+1,0);
	dp[0]=1; sum=0;
	rep(i,s)
	{
		sum+=time[i];
		for(int j=sum;j>=0;j--)
		if(dp[j])dp[j+time[i]]=1;
	}
	
	int ret=sum+1;
	rep(i,sum/2+1)if(dp[i]&&dp[sum-i])ret=min(ret,sum-i);
	return ret;
}

int main()
{
	while(cin>>n>>m,n)
	{
		map<string,int> cid;
		string t;
		rep(i,n)cin>>t,cid[t]=i;
		times.clear(); times.resize(n);
		rep(i,m)
		{
			int tmp; cin>>tmp>>t;
			times[cid[t]].pb(tmp);
		}
		int ans=0;
		rep(i,n)ans+=calc(i);
		cout<<ans<<endl;
	}
	return 0;
}