PKU演習問メモ(4/15)

別のタスクをするからPKUの演習量を減らしてるはずなのに別タスクが全然こなされてないぞ……いけないいけない！
や、以前の自分と比べたらPKU少しでもやってるだけマシと見るべきか。

今日はCodeforcesのラウンド。上手くWA出さずに100位以内に入れたらいいなー。

No.	Title	分類・解法	主観的難易度
2817	WordStack	ビットDP	★★☆☆☆
3048	Max Factor	素因数分解	★☆☆☆☆

2817 WordStack

問題概要

n個(n≦10)の単語が与えられる。このとき、各単語の先頭に好きなだけスペースを挿入して、できるだけ「すぐ上に自分と同じ文字がある」ような文字の数を増やしたい。
このような文字の最大数を求めよ。スペースは同じ文字とは数えず、単語は好きな順に使ってよい。また、それぞれの単語は10文字以下である。

解法

n=10なので総当りでいいんじゃないだろうか、とか思ってやったらTLEだったorz
ちゃんと効率のいい解法で解く必要がある。

ある単語とその上の単語の文字の「一致数」は、２つの単語だけを決めれば一つに決まることに注目する。すると単語と単語の「一致数」を事前に計算しておけば、単語の並べ替えに対して一致数の和を最大にするような問題に還元できるが、これは巡回セールスマン問題と同タイプの問題である。
（各単語をグラフの頂点、それぞれの一致数をグラフの辺と見る）
（巡回セールスマン問題は最後に出発点に戻ってくるというところが違う）

なので、巡回セールスマン問題と同じようにビットを用いた動的計画法を書けばよい。
計算時間はO(2^n n)である。この辺がわからない人はiwiwi先生のスライドに丁寧な解説があるので参照！

ソースコード

int n,len[10],sc[10][10];
string str[10];
int calc(int a,int b)
{
	int ret=0;
	for(int j=-len[a]-len[b];j<len[a]+len[b];j++)
	{
		int c=0;
		rep(i,len[b])if(0<=j+i&&j+i<len[a]&&str[a][j+i]==str[b][i])c++;
		ret=max(ret,c);
	}
	return ret;
}

int ans,vis,opt[1024][10];
void rec(int c,int bit,int sum)
{
	if(bit==(1<<n)-1)
	{
		ans=max(ans,sum); return;
	}
	
	rep(i,n)if(!(bit&1<<i))
	{
		int nbit=bit|1<<i;
		if(opt[nbit][i]<sum+sc[c][i])
		{
			opt[nbit][i]=sum+sc[c][i];
			rec(i,nbit,opt[nbit][i]);
		}
	}
}

int main()
{
	
	while(cin>>n,n)
	{
		rep(i,n)cin>>str[i],len[i]=str[i].size(),sc[i][i]=0;
		rep(i,n)rep(j,i)sc[i][j]=sc[j][i]=calc(i,j);
		
		rep(i,1<<n)rep(j,n)opt[i][j]=0;
		ans=0;
		rep(i,n)rec(i,1<<i,0);
		
		cout<<ans<<endl;
	}
	return 0;
}

3048 Max Factor

問題概要

N個の数のうち、その最大の素因数が最も大きい数を答えよ。
ただしN≦5000であり、それぞれの数は20000以下である。

解法

Nも数も小さいので、2から順に整数で割れるだけ割ってやり、最後に割った数が最大の素因数という計算方針で間に合う。

ソースコード

int main()
{
	int n,mx=1,ans=1; cin>>n;
	rep(i,n)
	{
		int num; cin>>num;
		int t=num,f=0;
		for(int j=2;j*j<=t;j++)while(t%j==0)t/=j,f=j;
		if(t>1)f=t;
		if(mx<f)mx=f,ans=num;
	}
	cout<<ans<<endl;
	
	return 0;
}

なんか読みにくい……