PKU演習問メモ(9/3) - simezi

No.	問題名	問題の種類および解法	難易度
1789	Truck History	最小全域木	★★☆☆☆
1797	Heavy Transportation	ダイクストラ法	★★☆☆☆
1742	Coins	動的計画法（ナップサック問題）	★★★★☆
1856	Sea Battle	実装	★★☆☆☆
1850	Code	場合の数	★★★★☆

1789 Truck History

問題概要

n種類のトラックがあり、それぞれ英小文字7文字からなる識別コードがある。
全てのトラックは、他のトラックから派生してできたものである。（最初のひとつは除く）

"possible quality"を1/Σ[o,d]d(o,d)とするとき、その値を最大にするような派生のシナリオでの最大値を求めよ。
d(o,d)はトラックoとトラックdの識別コードにおいて、同じ位置にあり異なる文字の個数である。
Σ[o,d]とは全ての派生元と派生先のトラックのペアを表す。

解法

問題文がわかりにくいが、d[i][j]を識別コードの字数の違いとしたときの、グラフの最小全域木を求めよと言っているだけ。

なので、Prim法やKruskal法を使えばよい。

久々にPrimも書いてみた。せっかくなのでKruskalと速度比較してみた。
KruskalのUnion-Findは経路圧縮しかしていない。

Primのほうが大分速いみたい？しかもPrimのほうがタイプ量少ないのね。

ソースコード

Prim法（1047MS）

int n,d[2000][2000];
char c[2000][8];

int main()
{
	while(scanf("%d",&n),n)
	{
		rep(i,n)scanf("%s",c[i]);
		rep(i,n)rep(j,i)
		{
			int cnt=0;
			rep(k,7)if(c[i][k]!=c[j][k])cnt++;
			d[i][j]=d[j][i]=cnt;
		}
		
		int ans=0;
		bool v[2000]={0};
		priority_queue<pi> Q; Q.push(mp(0,0));
		rep(i,n)
		{
			int cur=Q.top().second,cc=-Q.top().first; Q.pop();
			
			if(v[cur])
			{
				i--; continue;
			}
			v[cur]=1; ans+=cc;
			
			rep(j,n)if(!v[j])Q.push(mp(-d[cur][j],j));
		}
		printf("The highest possible quality is 1/%d.\n",ans);
	}
	return 0;
}

Kruskal法（1782MS）

int n,m,p[2000];
char c[2000][8];

int root(int x)
{
	if(x==p[x])return x;
	return p[x]=root(p[x]);
}
int main()
{
	while(scanf("%d",&n),n)
	{
		rep(i,n)scanf("%s",c[i]);
		m=n*(n-1)/2;
		vector<pair<int,pi> > e; e.reserve(m);
		rep(i,n)rep(j,i)
		{
			int cnt=0;
			rep(k,7)if(c[i][k]!=c[j][k])cnt++;
			e.pb(mp(cnt,mp(i,j)));
		}
		sort(all(e));
		
		int ans=0,l=1;
		rep(i,n)p[i]=i;
		rep(i,m)
		{
			int a=e[i].second.first,b=e[i].second.second;
			a=root(a); b=root(b);
			if(a==b)continue;
			p[b]=a; l++; ans+=e[i].first;
			if(l==n)break;
		}
		printf("The highest possible quality is 1/%d.\n",ans);
	}
	return 0;
}

1797 Heavy Transportation

問題概要

n個の町をm個の双方向に通行可能な道路が結んでいる。
ただし、道路にはそれぞれ重量制限がある。

0番の町からn-1番の町へ行く路の中で、もっとも多くの重量を運べるような路における運べる重量を求めよ。

解法

どっかでやったような。
ダイクストラ法というかプリム法というかの典型問。
通常のダイクストラでは、prioriry_queueを並べ替えるのは、スタートのノードからの距離。ここでは"道の重さ"によりpriority_queueを並べ替える。

ソースコード

int n,m;
bool v[1000];

int main()
{
	int cs; scanf("%d",&cs);
	rep(CS,cs)
	{
		scanf("%d%d",&n,&m);
		vector<vector<pi> > e(n);
		rep(i,m)
		{
			int a,b,c; scanf("%d%d%d",&a,&b,&c); a--; b--;
			e[a].pb(mp(b,c)); e[b].pb(mp(a,c));
		}
		printf("Scenario #%d:\n",CS+1);
		
		int ans=0;
		rep(i,n)v[i]=0;
		priority_queue<pi> Q; Q.push(mp(inf,0));
		while(!Q.empty())
		{
			int mx=Q.top().first,c=Q.top().second; Q.pop();
			
			if(v[c])continue; v[c]=1;
			if(c==n-1)
			{
				ans=mx; break;
			}
			
			fr(i,e[c])if(!v[i->first])Q.push(mp(min(mx,i->second),i->first));
		}
		printf("%d\n\n",ans);
	}
	return 0;
}

1742 Coins

問題概要

n種類の硬貨がある。今、硬貨1,2,3……の額A1,A2,A3……およびそれぞれの所持している枚数C1,C2,C3……が与えられる。

このとき、手持ちの硬貨でおつりを出さずに支払える、1以上m以下の金額はいくつあるか。

n≦100,m≦100000を満たす。

解法

工夫しないDP（O(n*m*C)だとTLEだった）
O(n*m)が必要な模様。

これをO(n*m)をアルゴリズムは次のようなもの。
ok[i]に、今までの硬貨でiの金額を作れるかをもっておく。
dp[i][0]に、iを支払うために使ったもっとも番号が大きい硬貨の番号を、dp[i][1]にiを支払うために使った、最後の種類の硬貨枚数をもっておく。

そしてそれぞれの硬貨についてa[i]からmまでok[]の表を埋めていく。

ソースコード

int n,m,a[100],c[100];
bool ok[100001]; int dp[100001][2];

int main()
{
	while(scanf("%d%d",&n,&m),n)
	{
		rep(i,n)scanf("%d",a+i);
		rep(i,n)scanf("%d",c+i);
		rep(i,m+1)ok[i]=0,dp[i][0]=-1; ok[0]=1;
		
		int ans=0,prev;
		rep(i,n)
		{
			for(int j=a[i];j<=m;j++)
			if(!ok[j]&&ok[prev=j-a[i]]&&!(dp[prev][0]==i&&dp[prev][1]==c[i]))
			{
				ok[j]=1; ans++;
				dp[j][1]=dp[prev][0]==i?dp[prev][1]+1:1;
				dp[j][0]=i;
			}
		}
		printf("%d\n",ans);
	}
	
	return 0;
}

1856 Sea Battle

問題概要

nxmのグリッドであらわされる海があり、'.'はそのグリッドが空であることを、'#'はそのグリッドに船があることを意味する。

全ての船は長方形をしているとしてよく、またグリッド上の#の長方形は一隻の船であるとしてよい。
今、海の状態が与えられたとき、船が頂点同士または辺同士で接触している場合は"Bad placement."を、そうでない場合は船の数の合計を求めよ。

解法

接触がない場合は単なる島数えの問題で、再帰による塗りつぶしで解ける。

船同士の接触はどう判定するかというと、船と船が接触すれば必ず"角"ができる

#.
.#
↑こんなの

したがって、各"."のマスについて、上下左右に角ができてないかを探すことで、接触の判定もできる。

ソースコード

void nul(int y,int x)
{
	sea[y][x]='.';
	rep(d,4)
	{
		int ny=y+dy[d],nx=x+dx[d];
		if(ny<0||ny>=h||nx<0||nx>=w)continue;
		if(sea[ny][nx]=='#')nul(ny,nx);
	}
}

int main()
{
	while(scanf("%d%d",&h,&w),h)
	{
		rep(i,h)scanf("%s",sea[i]);
		
		int ans=0; char cell[4];
		rep(i,h)rep(j,w)if(sea[i][j]=='.')
		{
			rep(d,4)
			{
				int ny=i+dy[d],nx=j+dx[d];
				if(ny<0||ny>=h||nx<0||nx>=w)cell[d]='.';
				else cell[d]=sea[ny][nx];
			}
			
			rep(d,4)if(cell[d]=='#'&&cell[d+1&3]=='#')
			{
				puts("Bad placement."); goto END;
			}
		}
		
		rep(i,h)rep(j,w)if(sea[i][j]=='#')
		{
			ans++; nul(i,j);
		}
		printf("There are %d ships.\n",ans);
		
		END:;
	}
	
	return 0;
}

1850 Code

問題概要

英小文字からなるwordに対応する順序を求めよ。
wordは10文字以下の異なる英小文字が、昇順でいくつか並んだものである。

長さの違うものは短いものが順序が前
長さの同じものは、辞書順で前に来るものが順序が前

例

a 1
z 26
ab 27
vwxyz 83681

与えられたwordが間違ったものである場合は0を出力せよ。

解法

主観的難易度がやたら高いのは自分が数学苦手だから。
こういうのすらすら解ける人ってうらやましいわー。

まず、与えられたwordと同じ文字数で、一番前に来るのが何番目になるかを調べる。
それはより短いword全ての個数を足せばよい。つまりΣ26Ci

で、次に、wordの先頭がaで、その長さのものがいくつあるかを足し、
bで……と、先頭の文字にたどり着くまで個数を足す。
次の文字も同様のことを繰り返す。

ソースコード

int C[30][30];

int main()
{
	rep(i,30)rep(j,i+1)
	{
		if(i==0||j==0||i==j)C[i][j]=1;
		else C[i][j]=C[i-1][j]+C[i-1][j-1];
	}
	char str[11]; gets(str);
	int l=strlen(str);
	
	rep(i,l-1)if(str[i]>=str[i+1])
	{
		puts("0"); return 0;
	}
	
	
	int ans=1;
	for(int i=1;i<l;i++)ans+=C[26][i];
	char prev='a';
	rep(i,l)
	{
		while(prev<str[i])ans+=C[25-prev+'a'][l-i-1],prev++;
		prev++;
	}
	printf("%d\n",ans);
	
	return 0;
}