PKU演習問メモ(4/8)

ICPC

今日は25:00からCodeforcesのラウンド。起きてられるかなあ。

No. Title 分類・解法
1488 TEX Quotes String manipulation
2366 Sacrament of the sum Straight forward
2552 Assistance Required Straight forward
2509 Peter's smokes Straight forward
2601 Simple calculations Math, Bisection method
1160 Post Office Dynamic Programming
1274 The Perfect Stall Maximum matchings in bipartite graph

1488 TEX Quotes

問題概要

与えられた文字列の奇数番目の"(ダブルクオート)を``(バッククオート二つ)に、偶数番目の"を''(シングルクオート二つ)に置換せよ。

解法

一行ずつ読んで置換して出力。
C++の人は自前でメソッドを書く。

ソースコード
bool begin=1;
void rpl(string &s)
{
	for(int p=0;(p=s.find('"',p))!=s.npos;p++)
	{
		s=s.substr(0,p)+(begin?"``":"''")+s.substr(p+1);
		begin^=1;
	}
}

int main()
{
	string str;
	while(getline(cin,str))rpl(str),cout<<str<<endl;
	
	return 0;
}

2366 Sacrament of the sum

問題概要

二つの数の表が与えられる。表1と表2から和が10000になるように一つずつ数を選ぶことができるかを答えよ。
ただし与えられる数は-32768以上32767以下とする。

解法

与えられる数は数が多くて（たぶん）、範囲が狭いので65536個の配列を2つ作る。
それぞれの数が一度以上現れたかを記録しておき、現れた数同士で和が10000になりうるものがあるかどうかを見れば32768回のループで済む。

ソースコード
int n,m;
bool num1[65536],num2[65536];

int main()
{
	scanf("%d",&n);
	rep(i,n)
	{
		int a; scanf("%d",&a);
		num1[a+32768]=1;
	}
	scanf("%d",&m);
	rep(i,m)
	{
		int a; scanf("%d",&a);
		num2[a+32768]=1;
	}
	
	for(int i=-32768;i<32768;i++)if(num1[i+32768])
	{
		int j=10000-i;
		if(-32768<=j&&j<32768&&num2[j+32768])
		{
			cout<<"YES"<<endl; return 0;
		}
	}
	cout<<"NO"<<endl;
	
	return 0;
}

2552 Assistance Required

問題概要

一列に並んだ人に対して2,3,4,5...と番号を渡す。列の一番最初の人の番号を見る。
2であり、その人は皿洗いを免れるが2つ次の人（4番）、4つ次の人（6番）...は皿洗いをしなければならない。
次に列の二番目の人の番号を見る。3でありその人は皿洗いを免れるが3つ次の人（9番）、6つ次の人（15番）...は皿洗いをしなければならない。


このような操作を十分繰り返した後、列のn番目の人が持っている番号を答えよ。

解法

エラトステネスのふるいっぽいが、列に並んでいる人に対して消す操作を行うことに注意。
素直にvectorに4万まで入れて順次消していった。vectorの要素削除はo(n)なので結構TLEが怪しいような気がしたが通ってしまった。
（一応2の倍数は最初から消しておくなど姑息なことをした）


多分もっとよい解法があるはず。というかCだとどう書くんだろう……実行時間トップはサイズを見るにどうみても埋め込みｗ

ソースコード
int main()
{
	vi ans(20000);
	for(int i=1;i<20000;i++)ans[i]=i*2+1; ans[0]=2;
	for(int i=1;i<ans.size();i++)
	{
		for(int j=i+ans[i];j<ans.size();j+=ans[i]-1)
			ans.erase(ans.begin()+j);
	}
	
	int n;
	while(cin>>n,n)cout<<ans[n-1]<<endl;
	
	return 0;
}

2509 Peter's smokes

問題概要

n本のたばこがある。k本の吸殻からまた新たに1本のたばこを作ることができる。
n,kが与えられた時合計で何本のたばこを吸うことができるか求めよ。

解法

問題文を5回くらい読み直して漸く意味がわかった……


吸殻から作ったたばこを吸うとまた吸殻が発生する。
吸殻の数がk本以上あるうちはループ。

ソースコード
int main()
{
	int n,k;
	while(cin>>n>>k)
	{
		int ans=n,r=n;
		for(;r>=k;)ans+=r/k,r=r%k+r/k;
		cout<<ans<<endl;
	}
	return 0;
}

2601 Simple calculations

問題概要

各項の間に次の関係がある数列aがある。
a[i]=(a[i+1]+a[i-1])/2-c[i]
a[0],a[n+1],数列cが与えられた時a[1]を求めよ。

解法

漸化式があるので解けば直接a[1]とa[n+1],a[0]の関係が求まる……ような気がするが解けなかったので二分法で通りそうなので二分法でやった。誰か解いた人教えてください……（ボソ


決めうちしたa[1]が増加するとa[n+1]も増加するため二分法が適用可能である。
a[n+1]は関係式を変形して順次求めていけばよい。

ソースコード
int n;
double a0,an1,c[3000];

double calc(double a1)
{
	double a=a1,aprev=a0,tmp;
	rep(i,n)
	{
		tmp=a;
		a=(a+c[i])*2-aprev;
		aprev=tmp;
	}
	
	return a;
}

int main()
{
	cin>>n>>a0>>an1;
	rep(i,n)cin>>c[i];
	
	double lo=-1000,hi=1000,ans;
	rep(i,100)
	{
		ans=(lo+hi)/2;
		if(calc(ans)>an1)hi=ans;
		else lo=ans;
	}
	
	printf("%.2f\n",ans);
	
	return 0;
}

1160 Post Office

問題概要

v個の村が数直線上にある。各村から最寄の郵便局までの距離の総和が最小になるように郵便局をp個つくりたい。
v,pと各村の座標が与えられるとき、最寄の郵便局までの距離の総和の最小値を求めよ。

解法

vCp通り試すと明らかに宇宙が終わるまで計算しても終了しないので、動的計画法が見えてくる。村iにj個目の郵便局を建てたときの、村iより左側の部分の距離の総和をdp[i][j-1]とすると、
dp[i][j-1]=min{dp[k][j-2]+(村iから村kの、最寄の郵便局までの距離の総和)}
となる。あとはp個郵便局を建て終わった後で、それより右側の村の距離の総和を足してやればよい。


「村iから村kの、最寄の郵便局までの距離の総和」はあらかじめ計算しておかないとTLEになる（なった）。計算しておくことでO(pv^2)の計算量で最適解を求めることが可能になる。

ソースコード
int v,p,X[300];
int dp[300][30],cost[300][300];

int main()
{
	cin>>v>>p;
	rep(i,v)cin>>X[i];
	
	rep(i,v)rep(j,i)for(int k=j;k<i;k++)
		cost[j][i]+=min(X[i]-X[k],X[k]-X[j]);
	
	rep(i,v)rep(j,p-1)dp[i][j+1]=inf;
	rep(i,v)rep(j,i)
		dp[i][0]+=X[i]-X[j];
	
	for(int i=1;i<v;i++)for(int j=1;j<min(i,p);j++)rep(k,i)
		dp[i][j]=min(dp[i][j],dp[k][j-1]+cost[k][i]);
	
	for(int i=p-1;i<v;i++)for(int j=i+1;j<v;j++)
		dp[i][p-1]+=X[j]-X[i];
	
	int ans=inf;
	rep(i,v)ans=min(ans,dp[i][p-1]);
	cout<<ans<<endl;
	
	return 0;
}

1274 The Perfect Stall

問題概要

牛小屋にm個の部屋があり、n頭の牛がいる。牛は自分の好きな部屋でしかミルクを出さず、また一つの部屋には一頭の牛しか入れない。ミルクを出す牛を最大にするような部屋の割り当て方をしたときの、ミルクを出す牛の数を求めよ。

解法

牛と好きな部屋の関係を二部グラフと見ることができるので、二部グラフの最大マッチングで解ける。
二部グラフの最大マッチングは割と有名問題なので、知らない人はwebサイトや本など参照にするとよい。たぶん載ってる。

ソースコード
int n,m;
bool e[400][400];
int p[400],ans;
bool V[400];

bool rec(int s)
{
	if(s<0)return 1;
	for(int i=s<n?n:0;i<(s<n?n+m:n);i++)if(!V[i]&&e[s][i])
	{
		V[i]=1;
		if(rec(p[i]))return p[s]=i,p[i]=s,1;
	}
	return 0;
}
int main()
{
	while(cin>>n>>m)
	{
		rep(i,n+m)fill(e[i],e[i]+n+m,0);
		
		rep(i,n)
		{
			int k; cin>>k;
			rep(j,k)
			{
				int t; cin>>t; t+=n-1;
				e[i][t]=e[t][i]=1;
			}
		}
		
		fill(p,p+m+n,-1);
		ans=0;
		rep(i,n)
		{
			fill(V,V+m+n,0);
			if(rec(i))ans++;
		}
		cout<<ans<<endl;
	}
	return 0;
}