PKU演習問メモ(8/7)

PKU

もう僕頭悪すぎてだめかも。生きてても仕方ねえ……

No. 問題名 問題の種類および解法 難易度
1836 Alignment 動的計画法(最長増加部分列) ★★★☆☆
1770 Special Experiment メモ化再帰(Tree DP) ★★☆☆☆
1661 Help Jimmy 動的計画法 ★★☆☆☆
1038 Bugs Integrated, Inc. 二重深さ優先探索 ★★★★☆
3265 Problem Solving 動的計画法 ★★★☆☆
1036 Gangsters 動的計画法 ★★☆☆☆
3666 Making the Grade 座標圧縮・二段DP ★★★★★
2404 Jogging Trails 無向中国人郵便配達問題 ★★★★★

1836 Alignment

問題概要

一列になっているn人の身長が与えられる。
この中から何人か取り除き、残りの人で（順序を変えず）新しい列を作る。
このような列のうち、全ての人が左端または右端のどちらかの人を見ることができるようなものの、最長のものの長さをもとめよ。


ただし、端の人が見えるとは、その人と端の人との間に、自分以上の身長の人がいないことを言う。

解法

7WAとか久しぶり……まず題意がよくつかめないし……
という訳で解法ぐぐった。


増加部分列を二個合わせたものを求めればよいらしい。

ソースコード
int n;
double h[1000];
int dp[1000],dp2[1000];

void solve(int *d)
{
	rep(i,n)d[i]=1;
	rep(i,n)rep(j,i)if(h[j]<h[i])d[i]=max(d[i],d[j]+1);
}

int main()
{
	cin>>n;
	rep(i,n)cin>>h[i];
	solve(dp);
	reverse(h,h+n); solve(dp2); reverse(dp2,dp2+n);
	
	int ans=0;
	rep(i,n)for(int j=i+1;j<n;j++)ans=max(ans,dp[i]+dp2[j]);
	cout<<n-ans<<endl;
	
	return 0;
}

1770 Special Experiment

問題概要

原子には複数のエネルギー状態があり、原子はエネルギー状態間を、エネルギーの差に等しい光子を授受することで、エネルギー状態間を遷移する。

ここで、次のような原子を考える。
あるエネルギー状態間は直接遷移することができるが、あるエネルギー状態間は直接遷移することができない。
直接遷移することができないエネルギー状態は、Ei1,Ei2,……,Eikという風に途中いくつかの状態を経由して遷移するが、この原子においてその遷移の仕方は一意である。
また、EikからEi1に遷移する際は、上の経路を逆に辿って遷移する。


この原子のN個のエネルギー状態と、吸収する光子のエネルギーM種類が与えられたとき、
箱にこの原子を以下の条件を満たすようにつめる。このとき、箱の中の原子のエネルギーの和の最大値を求めよ。
ただしN,M≦200を満たす。

  • どの二つの原子のエネルギーも等しくない。
  • どの二つの原子も、一方が1つの光子の授受でもう一方へ遷移するエネルギー状態にない。
解法

問題読解ゲー。
要するに、原子のエネルギーをグラフとして見て、隣り合わない頂点を、和を最大にして選ぶという問題。
更に、問題文の条件からこのグラフは木または森になることがいえる。
（またこんな問題か……）


という訳で木をメモ化探索なりすればよい。

ソースコード
int n,m;
ll ene[200],dp[200][2];
vector<vi> e;

int rec(int c,int p,bool puse)
{
	if(dp[c][puse]>=0)return dp[c][puse];
	
	int ret=0,tmp;
	if(!puse)
	{
		tmp=ene[c];
		fr(i,e[c])if(*i!=p)tmp+=rec(*i,c,1);
		ret=max(ret,tmp);
	}
	tmp=0;
	fr(i,e[c])if(*i!=p)tmp+=rec(*i,c,0);
	ret=max(ret,tmp);
	
	return dp[c][puse]=ret;
}
int main()
{
	while(cin>>n>>m,n)
	{
		rep(i,n)cin>>ene[i];
		set<ll> diff; ll t;
		rep(i,m)cin>>t,diff.insert(t);
		
		e.clear(); e.resize(n);
		rep(i,n)rep(j,i)if(diff.count(ABS(ene[i]-ene[j])))
			e[i].pb(j), e[j].pb(i);
		rep(i,n)rep(j,2)dp[i][j]=-1;
		
		ll ans=0;
		rep(i,n)if(dp[i][0]<0)ans+=rec(i,-1,0);
		cout<<ans<<endl;
	}
	
	return 0;
}

1661 Help Jimmy

問題概要

JimmyがX,Yの地点から、地面まで降りる。
床に接していない間はJimmyは1m/sの速度で真下に落下し、床の上にいるときは左または右に1m/sで走る。


Jimmyが降りることのできる最大の高さはMAXで与えられ、それより大きな距離を落下すると死んでしまう。
N枚の床の情報が左端および右端の座標X1[i],X2[i],高さH[i]で与えられるとき、Jimmyが死なずに高さ0の地面まで降りるのにかかる最短時間を求めよ。

  • 20000≦X,X1[i],X2[i]≦20000かつ

0≦H[i],Y≦20000である。
0高さの高さには無限に広い直線（地面）があるものとする。
また、解は必ず存在することが保証されている。

解法

i番目の板の左端または右端にたどり着く最短時間をdp[i][j]として動的計画法。
板を高さの順にソートしておくことで、（落ちる板は自分より添え字が大きいものだけになるため）計算量が減る。


問題文には書かれていないが、板の境界にも乗ることができて、
たとえば1 10 20の板と1 10 10の板があったとすると、上の板から下の板へ飛び移ることができる。（酷い）

ソースコード

酷いｗ着地の判定もう少しなんとかならないだろうか。

struct S{
	int x1,x2,y;
	bool operator<(const S &r)const{
		return y>r.y;
	}
};
int n,X,Y,h;
S yuka[1000];
int dp[1000][2];

int main()
{
	int cs; scanf("%d",&cs);
	while(cs--)
	{
		scanf("%d%d%d%d",&n,&X,&Y,&h);
		rep(i,n)scanf("%d%d%d",&yuka[i].x1,&yuka[i].x2,&yuka[i].y);
		sort(yuka,yuka+n);
		
		rep(i,n)rep(j,2)dp[i][j]=inf;
		int c=0;
		for(;c<n;c++)if(yuka[c].y<=Y&&yuka[c].x1<=X&&X<=yuka[c].x2)break;
		if(c==n)
		{
			printf("%d\n",Y);
			continue;
		}
		
		int ans=inf;
		dp[c][0]=X-yuka[c].x1+Y-yuka[c].y; dp[c][1]=yuka[c].x2-X+Y-yuka[c].y;
		for(;c<n;c++)
		{
			int a=c+1,b=c+1;
			for(;a<n;a++)if(yuka[a].y<=yuka[c].y&&
				yuka[a].x1<=yuka[c].x1&&yuka[c].x1<=yuka[a].x2)break;
			if(a==n)
			{
				if(yuka[c].y<=h)ans=min(ans,dp[c][0]+yuka[c].y);
			}
			else if(yuka[c].y-yuka[a].y<=h)
			{
				int t=yuka[c].y-yuka[a].y+dp[c][0];
				dp[a][0]=min(dp[a][0],t+yuka[c].x1-yuka[a].x1);
				dp[a][1]=min(dp[a][1],t+yuka[a].x2-yuka[c].x1);
			}
			
			for(;b<n;b++)if(yuka[b].y<=yuka[c].y&&
				yuka[b].x1<=yuka[c].x2&&yuka[c].x2<=yuka[b].x2)break;
			if(b==n)
			{
				if(yuka[c].y<=h)ans=min(ans,dp[c][1]+yuka[c].y);
			}
			else if(yuka[c].y-yuka[b].y<=h)
			{
				int t=yuka[c].y-yuka[b].y+dp[c][1];
				dp[b][0]=min(dp[b][0],t+yuka[c].x2-yuka[b].x1);
				dp[b][1]=min(dp[b][1],t+yuka[b].x2-yuka[c].x2);
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

1038 Bugs Integrated, Inc.

問題概要

NxMのグリッドの長方形をしたウェーハーがある。
このなかのK個のグリッドには欠陥がある。
欠陥のない部分から、2x3の長方形のチップを出来るだけ多く取り出したい。
そのような最大の枚数は何枚か。


N≦150,M≦10

解法

一行ごとに、全てのチップの取り方を生成し、そこから再帰的に試す。（六角大蛇っぽい？）
下の二行の状態をビットで持っておくことで再帰関数の引数にできる。
特に枝刈りなどの計算量的な工夫をしなくても通る。


一応recはメモ化したけど効果あるんだろうか……

ソースコード
int h,w,k;
bool bad[150][10];

void gen(int y,int bit,int x,int nbit,int num,vector<pi> &s)
{
	if(x>=w-1)
	{
		s.pb(mp(nbit,num)); return;
	}
	if(y+2<h&&x+1<w)	//tate
	{
		bool ok=1;
		rep(i,3)rep(j,2)if(bad[i+y][j+x]||i<2&&(bit&1<<i*w+j+x))ok=0;
		if(ok)
		{
			int nnbit=nbit;
			rep(i,2)rep(j,2)nnbit|=1<<i*w+j+x;
			gen(y,bit,x+2,nnbit,num+1,s);
		}
	}

	if(y+1<h&&x+2<w)	//yoko
	{
		bool ok=1;
		rep(i,2)rep(j,3)if(bad[i+y][j+x]||(bit&1<<i*w+j+x))ok=0;
		if(ok)
		{
			int nnbit=nbit;
			rep(i,3)nnbit|=1<<i+x;
			gen(y,bit,x+3,nnbit,num+1,s);
		}
	}
	gen(y,bit,x+1,nbit,num,s);
}

map<pi,int> dp;

int rec(int cur,int bit)
{
	if(cur+1>=h)return 0;
	if(dp.count(mp(cur,bit)))return dp[mp(cur,bit)];
	
	vector<pi> states; gen(cur,bit,0,bit>>w,0,states);
	int ret=0;
	fr(i,states)ret=max(ret,rec(cur+1,i->first)+i->second);
	
	return dp[mp(cur,bit)]=ret;
}
int main()
{
	int d; scanf("%d",&d);
	while(d--)
	{
		scanf("%d%d%d",&h,&w,&k);
		rep(i,h)rep(j,w)bad[i][j]=0;
		rep(i,k)
		{
			int y,x; scanf("%d%d",&y,&x);
			bad[y-1][x-1]=1;
		}
		dp.clear();
		printf("%d\n",rec(0,0));
	}
	
	return 0;
}

3265 Problem Solving

問題概要

P個の問題をコンサルタントに依頼して解決する。問題は1番,2番,……と順に解決する必要がある。
それぞれの問題のコンサルタントに対する報酬は、手付金がb[i]、解決後の報酬がa[i]である。


一月の収入はMであるが、収入を溜めておくことはできない。
このとき、問題を最短で何ヶ月で解決できるか、求めよ。


P≦300,M≦1000を満たす。

解法

PもMも小さいため、dp[i][j]に、「i月において、解決後の報酬をj払うことになっている時の解決問題数の最大値」を持てる。
すると漸化式が立つので動的計画法ができる。


サンプルが貧弱なのでミスを起こしやすいorz

ソースコード
int m,p;
int b[300],a[300];
int dp[900][1001];

int main()
{
	scanf("%d%d",&m,&p);
	rep(i,p)scanf("%d%d",b+i,a+i);
	
	for(int i=2;;i++)rep(j,m+1)
	{
		int c=dp[i][j],money=m-j,next=0;
		
		if(c==p)
		{
			printf("%d\n",i); goto END;
		}
		dp[i+1][0]=max(dp[i+1][0],c);
		
		while(c<p&&money>=b[c]&&next+a[c]<=m)
		{
			money-=b[c]; next+=a[c];
			dp[i+1][next]=max(dp[i+1][next],++c);
		}
	}
	END:
	return 0;
}

1036 Gangsters

問題概要

n人のギャングがレストランに来る。
レストランの営業時間はT秒であり、レストランにはドアがある。
ドアには開き方の状態がKあり、1秒ごとに開き方は0以上K以下の間で、
1増やす、1減らす、あるいはそのままにすることができる。

n人のギャングはそれぞれ来店する時間がt[i]で決まっており、
なおかつ、ドアの開き方がs[i]でないと入店せずに帰ってしまう。


ギャングの格p[i]が与えられたとき、入店するギャングの格の和の最大値を求めよ。

解法

時間i、開き方jにおける最適解をdp[i][j]として動的計画法をすればよい。
そのままやるとメモリ制限にひっかかるので、表は2列分だけを持っておくようにする。
ギャングは入店時間で昇順にソートしておくと、線形探索をせずにすむ。

ソースコード
struct S{
	int t,p,s;
	bool operator<(const S &r)const{
		return t<r.t;
	}
};
S gang[100];
int n,k,t;
int dp[2][101];

int main()
{
	scanf("%d%d%d",&n,&k,&t);
	rep(i,n)scanf("%d",&gang[i].t);
	rep(i,n)scanf("%d",&gang[i].p);
	rep(i,n)scanf("%d",&gang[i].s);
	sort(gang,gang+n);
	
	rep(i,k+1)dp[0][i]=-inf;
	dp[0][0]=0;
	int c=0;
	for(;c<n&&gang[c].t==0;c++)if(gang[c].s==0)dp[0][0]+=gang[c].p;
	
	int cur=0,next=1;
	for(int i=1;i<=t;i++)
	{
		rep(j,k+1)
		{
			dp[next][j]=dp[cur][j];
			for(int jj=j-1;jj<j+2;jj++)if(0<=jj&&jj<k+1)
				dp[next][j]=max(dp[next][j],dp[cur][jj]);
		}
		
		for(;c<n&&gang[c].t<=i;c++)rep(j,k+1)
		if(gang[c].t==i&&gang[c].s==j)dp[next][j]+=gang[c].p;
		swap(cur,next);
	}
	printf("%d\n",*max_element(dp[cur],dp[cur]+k+1));
	
	return 0;
}

3666 Making the Grade

問題概要

長さnの数列が与えられる。
数列を、各項を変えることで単調非減少または単調非増加な数列{bn}に変えたい。
このときのコストはΣ|a[i]-b[i]|である。
コストの最小値を求めよ。


n≦2000,a[i]≦1000000000を満たす。

解法

解説ぐぐった。
ていうかこういう問題TopCoderのSRMで出たらとけねーぞ……


まず、a[i]を、数列{an}で使われてない数に変えることは不要である。
したがって、座標圧縮ができる。

そして、単調非増加の場合は項を逆順にすれば単調非減少の問題に帰着するので、単調非減少の場合だけを解けばよいこともわかる。


dp[i][j]に、項i番目が値jのときの最小コストを持っておく。
するとdp[i][j]=dp[i-1][k]+abs(a[i]-value[j])の関係からO(n^3)のDPができるが、これだと計算時間の制限に間に合わない。


ここで、kについて全てのループを見る必要は実はなくて、
dp2[i][j]にi番目の項で、「値がj以下の場合の最適解」を持ってけば、それをjのループの中で更新しつつ、dp[i][j]も更新することができ、O(n^2)で全体の計算ができる。


これをコードにしたのが以下。

ソースコード
int n,m,a[2000],v[2000];
ll dp[2000][2000],dp2[2000][2000];

ll solve()
{
	rep(i,n)rep(j,n)dp[i][j]=dp2[i][j]=inf;
	rep(i,n)
	{
		dp[0][i]=abs(v[i]-v[a[0]]);
		dp2[0][i]=min(dp[0][i],i>0?dp2[0][i-1]:inf);
	}
	for(int i=1;i<n;i++)
	{
		rep(j,m)
		{
			dp[i][j]=dp2[i-1][j]+abs(v[j]-v[a[i]]);
			dp2[i][j]=min(j>0?dp2[i][j-1]:inf,dp[i][j]);
		}
	}
	return *min_element(dp[n-1],dp[n-1]+m);
}

int main()
{
	scanf("%d",&n);
	rep(i,n)scanf("%d",a+i),v[i]=a[i];
	sort(v,v+n); m=unique(v,v+n)-v;
	rep(i,n)a[i]=lower_bound(v,v+m,a[i])-v;
	
	ll ans=solve();
	reverse(a,a+n);
	ans=min(ans,solve());
	printf("%lld\n",ans);
	
	return 0;
}

2404 Jogging Trails

問題概要
解法

全ての辺を1度以上通る閉路のうち、最も短いものを求める問題は、
無向中国人郵便配達問題といい、典型問らしい。
ライブラリが見つかったので使用。
（http://www.prefield.com/algorithm/graph/undirected_chinese_postman.html）


説明が良く解らなかったので多分今の自分には解けない問題だろう。

  • オイラー路になるように最も短い辺を補完（オイラー補完というらしい）
  • その後最小重みマッチング

という手順で解くらしい。最小重みマッチングもまだ勉強してない。

ソースコード
int main()
{
	int n,m;
	while(scanf("%d",&n),n)
	{
		scanf("%d",&m); Graph g(n);
		rep(i,m)
		{
			int a,b,c; scanf("%d%d%d",&a,&b,&c);
			a--; b--;
			g[a].pb(Edge(a,b,c)); g[b].pb(Edge(b,a,c));
		}
		printf("%d\n",chinesePostman(g));
	}
	return 0;
}