PKU演習問メモ(4/17) - simezi

No.	Title	分類・解法	主観的難易度
3250	Bad Hair Day	データ構造	★★★☆☆
2860	Block game with the Little Prince	貪欲法	★☆☆☆☆
3061	Subsequence	数列	★★★☆☆
2973	Scrabble	文字列・貪欲法	★★☆☆☆
2907	Collecting Beepers	巡回セールスマン問題	★★☆☆☆

以下問題概要、解説、ソースコード。

3250 Bad Hair Day

問題概要

n(n≦80000)匹の牛が一直線上に並んでいる。牛は自分より後ろの牛で、自分よりも背が低い牛の髪形を見ることができる。しかし、列に自分と同じかそれより背が高い牛がいた場合そこから後ろの牛の髪形は遮られて見ることはできない。

それぞれの牛の身長(1以上10^9以下)が与えられる。i番目の牛が髪形を見ることのできる牛の数をciとするときciの総和を求めよ。

解法

各牛について自分以上の背の牛が現れるまでループを回すO(n^2)の解法だとnが大きいためにおそらくTLE.
「今のところ自分を見ることのできる牛」の数を状態として持てないかということを考えると、スタックのデータ構造を使うことが思い浮かぶ。

具体的には、スタックにそれより前に出てきた自分より身長の高い牛を全て積んでおくようにすればいい。こうすることでO(n)でΣciを求めることが可能になる。
Σciは32bitの範囲を超えうることに注意。

ソースコード

int n,h[80000];

int main()
{
	scanf("%d",&n);
	rep(i,n)scanf("%d",h+i);
	
	stack<int> S;
	int s=0; ll ans=0;
	rep(i,n)
	{
		while(!S.empty()&&h[i]>=S.top())S.pop(),s--;
		ans+=s;
		S.push(h[i]),s++;
	}
	
	cout<<ans<<endl;
	
	return 0;
}

2860 Block game with the Little Prince

問題概要

N個の区別ない箱がK個の部屋に分かれて入っている。各部屋にはM個までの箱を入れることができる。
初期状態と最終状態でのそれぞれの各部屋に入っている箱の数が与えられた時、初期状態から箱をひとつずつ移動させて最終状態にするための最小の箱の移動回数を求めよ。

解法

初期状態と最終状態が同じ部屋については手を付ける必要はない。
箱の数が違う部屋だけ箱を移動する必要があるが、「箱の足りない部屋に箱が余っている部屋から持ってくる」と考えれば最低必要回数は明らかにその時の移動回数以上であり、逆にこの回数の移動で最終状態にできるので、これが最適解である。

ソースコード

int main()
{
	int n,m,k; cin>>n>>m>>k;
	int p[10];
	rep(i,k)cin>>p[i];
	
	int ans=0,q;
	rep(i,k)
	{
		cin>>q;
		if(p[i]>q)ans+=p[i]-q;
	}
	cout<<ans<<endl;
	
	return 0;
}

3061 Subsequence

問題概要

N個の数と自然数Sが与えられる。この数列の連続する部分数列で、項の和がSを超えるもののうちもっとも項数が少ないものの項の数を求めよ。

解法

これといい2860といい適切な分類がよく解らない。ナイーブな解法だとTLEになるような情報オリンピックっぽいアルゴリズム問題？（僕は情報オリンピックは知らないので想像）

さて、これも各項をスタートとしてSを超えるまで和を取っていくようなO(n^2)の解法が思い浮かぶがおそらくそれだとTLEになる。
一度Sを超えるまで和をとって、和がS以上の間左側の項を削っていく方針でも正しい解が求まる。これでO(n)で時間内に解ける。

ソースコード

int n,s,a[100000];

int main()
{
	int CS; scanf("%d",&CS);
	rep(cs,CS){
		scanf("%d%d",&n,&s);
		rep(i,n)scanf("%d",a+i);
		
		int ans=inf,sum=0,l=0;
		rep(i,n)
		{
			sum+=a[i];
			while(l<i&&sum>=s)ans=min(ans,i-l+1),sum-=a[l++];
		}
		printf("%d\n",(ans==inf?0:ans));
	}
	return 0;
}

2973 Scrabble

問題概要

与えられたアルファベットを使って辞書の単語のうちいくつを作れるかを求めよ。
ただし、与えられたアルファベットの中には"_"が入っていて、これはどの文字の代わりとしても良い。

解法

単語の文字のうち、与えられたアルファベットが使えるものはそれを使い、使えない文字に"_"を割り当てれば良い。
この考えを文字の出現回数を数えて実装してやればよい。

ソースコード

char str[1000][10];

int main()
{
	int n;
	while(cin>>n,n)
	{
		rep(i,n)cin>>str[i];
		char ch[10]; cin>>ch;
		
		int ccnt[256]={0};
		for(int i=0;ch[i];i++)ccnt[ch[i]]++;
		
		int ans=0;
		rep(i,n)
		{
			int cnt[256]={0},wc=ccnt['_'];
			for(int j=0;str[i][j];j++)cnt[str[i][j]]++;
			rep(j,256)
			{
				if(ccnt[j]<cnt[j])
				{
					if(wc>=cnt[j]-ccnt[j])wc-=cnt[j]-ccnt[j];
					else goto SKIP;
				}
			}
			ans++;
			SKIP:;
		}
		cout<<ans<<endl;
	}
	return 0;
}

2907 Collecting Beepers

問題概要

wxhのグリッドで表される平面上にロボットがいる。ロボットは上下左右に動いて平面のポケベルを全て拾って、最初の場所にもどる。
ロボットの座標と、各ポケベルの座標が与えられたときの最短パスの長さを求めよ。
ただし、平面の一辺の長さは20以下、ポケベルの数は10以下である。

解法

典型的な巡回セールスマン問題なので、訪問済みノードのビットと現在位置をもって動的計画法で解けばいい。

ソースコード

int n,h,w;
int d[11][11];
int cost[1<<11][11];

void rec(int bit,int c)
{
	rep(i,n)if(!(1<<i&bit))
	{
		int nbit=bit|1<<i;
		if(cost[nbit][i]<=cost[bit][c]+d[i][c])continue;
		cost[nbit][i]=cost[bit][c]+d[i][c];
		rec(nbit,i);
	}
}

int main()
{
	int CS; cin>>CS;
	rep(cs,CS)
	{
		int py[11],px[11];
		cin>>w>>h>>px[0]>>py[0]>>n;
		rep(i,n)cin>>px[i+1]>>py[i+1];
		
		n++;
		rep(i,n)rep(j,i)d[i][j]=d[j][i]=abs(px[i]-px[j])+abs(py[i]-py[j]);
		
		rep(i,1<<n)rep(j,n)cost[i][j]=inf;
		cost[0][0]=0;
		rec(0,0);
		
		cout<<"The shortest path has length "<<cost[(1<<n)-1][0]<<endl;
	}
	return 0;
}