PKU演習問メモ(8/17)

No. 問題名 問題の種類および解法 難易度
3049 Securing the Barn 深さ優先探索 ★★☆☆☆
3192 DNA Assembly 探索・文字列 ★★☆☆☆
3183 Stump Removal 貪欲法 ★★★☆☆
3629 Card Stacking シミュレーション ★☆☆☆☆
3174 Alignment of the Planets 幾何(同一直線上の判定) ★★☆☆☆
3233 Matrix Power Series 行列の級数の和 ★★★☆☆
3481 Double Queue シミュレーション ★★☆☆☆
3716 Panda's Birthday Present 条件付確率・期待値 ★★★★☆

3049 Securing the Barn

問題概要

C種類の英小文字が与えられる。これらを使ってできる、以下の条件を満たす長さLのパスワードを昇順にすべて出力せよ。

  • パスワードの各文字は全て異なり、各文字はアルファベット順に並んでいる
  • パスワードには最低1つの母音字(a,e,i,o,u)と、2つの子音字(それ以外)が含まれる


L≦15を満たす。

解法

深さ優先探索により全列挙すればよい。

ソースコード
struct S{
	char s[16];
	bool operator<(const S &r)const{
		return strcmp(s,r.s)<0;
	}
};
int L,C,nb,nc;
char bo[5],co[21];
bool bu[5],cu[21];
S tmp;
vector<S> ans;

void dfs(int b,int c)
{
	if(b+c==L)
	{
		if(b>0&&c>1)ans.pb(tmp);
		return;
	}
	rep(i,nb)if(!bu[i]&&(b+c==0||tmp.s[b+c-1]<bo[i]))
	{
		bu[i]=1; tmp.s[b+c]=bo[i];
		dfs(b+1,c); bu[i]=0;
	}
	rep(i,nc)if(!cu[i]&&(b+c==0||tmp.s[b+c-1]<co[i]))
	{
		cu[i]=1; tmp.s[b+c]=co[i];
		dfs(b,c+1); cu[i]=0;
	}
}

int main()
{
	scanf("%d%d",&L,&C);
	rep(i,C)
	{
		char t; scanf(" %c",&t);
		if(t=='a'||t=='e'||t=='i'||t=='o'||t=='u')bo[nb++]=t;
		else co[nc++]=t;
	}
	dfs(0,0); sort(all(ans));
	fr(i,ans)printf("%s\n",i->s);
	
	return 0;
}

3192 DNA Assembly

問題概要

'A','G','C','T'からなる、それぞれ7文字以下の文字列n個が与えられる。
これらを以下の操作により全て一度ずつ"結合させた"もののうち、最も短いものの長さを求めよ。


結合:
二つの文字列A,BにAの末尾とBの先頭で共通部分がある場合それらを一度省略できる。
例:TACA + ACAT -> TACATなど

n≦7を満たす。

解法

並べ替えの個数は7!≒5000通りしかないのでnext_permutationにより全て試して結合させてみればよい。


STLのstringを使うとTLE...
自前の構造体を使うと0MSでAC.なんか酷い。

ソースコード
struct S{
	char s[10];
	int len;
	bool operator<(const S &r)const{
		return strcmp(s,r.s)<0;
	}
};
int n;
S in[10];

void con(char *a,int &len,S &b)
{
	int i=min(len,b.len);
	for(;i>=0;i--)
	{
		rep(j,i)if(a[len-i+j]!=b.s[j])goto FAIL;
		break; FAIL:;
	}
	for(;b.s[i];i++)a[len++]=b.s[i];
}

int main()
{
	cin>>n;
	rep(i,n)cin>>in[i].s,in[i].len=strlen(in[i].s);
	sort(in,in+n);
	
	int ans=inf;
	do
	{
		char tmp[100]; int len=0;
		rep(i,n)con(tmp,len,in[i]);
		ans=min(ans,len);
	}while(next_permutation(in,in+n));
	cout<<ans<<endl;
	
	return 0;
}

3183 Stump Removal

問題概要

n個の切り株が一直線上に並んでいる。それぞれの高さはh[i]で与えられる。
これらを全て破壊したい。
ある切り株に爆弾を設置し、爆破すると、隣の切り株がそれより(真に)小さな高さであり続ける限り衝撃波が貫通して切り株が破壊される。


全ての切り株を破壊するのに必要な最小の爆弾の個数を求めよ。


n≦50000,h[i]≦10000を満たす。

解法

左の切り株から貪欲に破壊する。
h[0]>h[1]の場合h[0]を爆破する必要はなく、それ以外の場合は爆破する必要がある。
h[0]を爆破した場合、爆風が高さが減少する限り続く。


次に破壊されていない切り株から同様の操作を繰り返す。


自分が貪欲法苦手なので難易度高めに設定。

ソースコード
int n,h[50000];

int main()
{
	scanf("%d",&n);
	rep(i,n)scanf("%d",h+i);
	
	int last=-1;
	rep(i,n-1)
	{
		if(last==-1&&h[i]>=h[i+1])last=1,printf("%d\n",i+1);
		if(last==1&&h[i]<=h[i+1])last=-1;
	}
	if(last==-1)printf("%d\n",n);
	
	return 0;
}

3629 Card Stacking

問題概要

1からK番までのカードをN人に以下のような手順で配る。

  • 最初はディーラーの右隣の人に山の一番上のカードを配る
  • 配った後、山の一番上のカードを山の一番下に入れる操作をP回繰り返す
  • カードがなくなるまで反時計回りに上の配り方をする


このとき、ディーラーに来るカードの番号を昇順で出力せよ。

N≦200,K≦100000,P≦10を満たす。

解法

deque(両端キュー)を使いナイーブにシミュレーションして間に合う。
O(NKP).

ソースコード
int n,m,p,ans[50000];

int main()
{
	scanf("%d%d%d",&n,&m,&p);
	int cnt=0,r=m;
	deque<int> Q; rep(i,m)Q.pb(i+1);
	rep(i,m)
	{
		if(i%n==n-1)ans[cnt++]=Q.front();
		Q.pop_front(); r--;
		rep(j,p)Q.pb(Q.front()),Q.pop_front();
	}
	sort(ans,ans+cnt);
	rep(i,cnt)printf("%d\n",ans[i]);
	
	return 0;
}

3174 Alignment of the Planets

問題概要

平面上のn個の点の座標が与えられる。
これらのうち、一直線上にある3点の組を全て出力せよ。

座標の組は昇順にソートせよ。


n≦770を満たす。

解法

(i,j,k)をi≦j≦kのように並べるのかと思ったら
組自体を昇順に並べるという意味だった……


n^3のナイーブな解法で間に合う。

ソースコード
int n,X[770],Y[770];

bool coli(int a,int b,int c)
{
	int y1=Y[c]-Y[a],y2=Y[b]-Y[a];
	int x1=X[c]-X[a],x2=X[b]-X[a];
	
	return y1*x2==y2*x1;
}

int main()
{
	scanf("%d",&n);
	rep(i,n)scanf("%d%d",X+i,Y+i);
	
	int ans=0; vi a,b,c;
	rep(i,n)for(int j=i+1;j<n;j++)for(int k=j+1;k<n;k++)
	if(coli(i,j,k))a.pb(i),b.pb(j),c.pb(k),ans++;
	
	printf("%d\n",ans);
	rep(i,ans)printf("%d %d %d\n",a[i]+1,b[i]+1,c[i]+1);
	
	return 0;
}

3233 Matrix Power Series

問題概要

nxnの行列Aが与えられる。
S = A + A^2 + A^3 + …… + A^kとする。
Sの各成分をmで割った余りの行列B(Bij=Sij%m)を求めよ。


n≦30,
m<10000,
k≦10^9を満たす。

解法

繰り返し二乗法的なことをする。
すなわちS(k)=S(k/2)+A^(k/2)*S(k-2/k)の関係を利用すると、全体でO(n^3logk)の計算量でS(k)が求まる。


小さい部分は適当にメモ化。

ソースコード
int n,m,k;
struct M{
	int a[30][30];
	M operator*(const M &o)
	{
		M ret;
		rep(i,n)rep(j,n)rep(k,n)
			ret.a[i][j]=(ret.a[i][j]+a[i][k]*o.a[k][j])%m;
		return ret;
	}
	M operator+(const M &o)
	{
		M ret;
		rep(i,n)rep(j,n)ret.a[i][j]=(a[i][j]+o.a[i][j])%m;
		return ret;
	}
	M(){rep(i,n)rep(j,n)a[i][j]=0;}
};
M in;
map<int,M> dp,dp2;

M pw(int p)
{
	if(p==1)return in;
	if(dp2.count(p))return dp2[p];
	return dp2[p]=pw(p/2)*pw(p-p/2);
}
M rec(int p)
{
	if(p==1)return in;
	if(dp.count(p))return dp[p];
	return dp[p]=rec(p/2)+pw(p/2)*rec(p-p/2);
}
int main()
{
	scanf("%d%d%d",&n,&k,&m);
	rep(i,n)rep(j,n)scanf("%d",&in.a[i][j]);
	
	M ans=rec(k);
	rep(i,n)rep(j,n)printf("%d%c",ans.a[i][j],j==n-1?'\n':' ');
	
	return 0;
}

3481 Double Queue

問題概要

次のようなクエリを処理せよ。
1 k p 優先度pでkをキューに追加
2 キューのうち優先度が最も高いものを取り出し、そのkの値を出力する
3 キューのうち優先度が最も低いものを取り出し、そのkの値を出力する

解法

クエリの数が与えられていないが、結構大きなサイズのよう?
挿入削除が定数時間でできるlinked listを使うのが良い気がする。
(普通の配列だとTLEになるような気がする。試してない)


[追記]Treapというデータ構造(乱数を用いた二分探索木)を使うと速いらしい。

ソースコード
int main()
{
	int r;
	list<pi> L; list<pi>::iterator it;
	
	while(scanf("%d",&r),r)
	{
		int k,p;
		if(r==1)
		{
			scanf("%d%d",&k,&p);
			L.pb(mp(p,k));
			continue;
		}
		
		if(r==2)it=max_element(all(L));
		else it=min_element(all(L));
		
		if(it==L.end())puts("0");
		else
		{
			printf("%d\n",it->second);
			L.erase(it);
		}
	}
	return 0;
}

3716 Panda's Birthday Present

問題概要

次のような試行を考える。
四つの特別なサイコロがある。これらは、一番目の試行の開始前に、全ての面がランダムで赤または青になる。
四つのサイコロをふり、出た赤の面の数を記録することを2度行う。


2度の試行においてそれぞれで出た赤い面の数が与えられるとき、
3度目の試行で出る赤い面の数の期待値を求めよ。

解法

条件付確率の問題。
ベイズの定理は高校1年だか2年の数学でやるはず。
http://www004.upp.so-net.ne.jp/s_honma/probability/bayes.htmhttp://aoki2.si.gunma-u.ac.jp/lecture/Probability/Bayes.htmlあたりを参照)


まず、サイコロにi,j,k,l個赤い面が出来る確率Pを求める。
次に、そのようなサイコロを振ったときに赤い面がa,b個ずつ出る確率P2を求める。


上の計算からベイズの定理に従い、サイコロがi,j,k,lである確率が求められるので、そこから次のサイコロで出る期待値が計算できる。

ソースコード
double p[7][7][7][7],p2[7][7][7][7];

double calc(int a,int p,int q,int r,int s)
{
	if(a<0||a>4)return 0;
	int o[4]={0}; rep(i,a)o[3-i]=1;
	double ret=0;
	do
	{
		ret+=(o[0]?p:6-p)*(o[1]?q:6-q)*(o[2]?r:6-r)*(o[3]?s:6-s)*1.0/(6*6*6*6);
	}while(next_permutation(o,o+4));
	return ret;
}
int C(int n,int k)
{
	int ret=1;
	rep(i,k)ret*=n-i,ret/=i+1;
	return ret;
}

int main()
{
	double face[7];
	rep(i,7)face[i]=C(6,i)/pow(2.0,6);
	
	rep(i,7)rep(j,7)rep(k,7)rep(l,7)
	{
		int o[]={i,j,k,l}; sort(o,o+4);
		p[o[0]][o[1]][o[2]][o[3]]+=face[i]*face[j]*face[k]*face[l];
	}
	
	int cs; scanf("%d",&cs);
	while(cs--)
	{
		int a,b; scanf("%d%d",&a,&b);
		double tot=0,ans=0;
		
		rep(l,7)rep(k,l+1)rep(j,k+1)rep(i,j+1)
		{
			p2[i][j][k][l]=calc(a,i,j,k,l)*calc(b,i,j,k,l);
			tot+=p[i][j][k][l]*p2[i][j][k][l];
		}
		rep(l,7)rep(k,l+1)rep(j,k+1)rep(i,j+1)
		{
			ans+=(i+j+k+l)/6.0*p[i][j][k][l]*p2[i][j][k][l]/tot;
		}
		
		printf("%.3f\n",ans);
	}
	return 0;
}