PKU演習問メモ(2010/3/29)

id:iwiwiさんがこんなのを公開して下さったようです。
DPと木のデータ構造って僕が今一番苦戦してるとこじゃないか!なんという神。


JOI 春合宿での講義資料(http://d.hatena.ne.jp/iwiwi/20100328)


多分おとといのCodeforces Round#6のEはちょうどこのデータ構造を問うている問題。後で解きなおしてみよう……


さて今日通した問題のメモ。

2245 Lotto
集合Sの部分集合のうち要素が6つのものを昇順に列挙する問題。再帰で探索するように書いて、最後に何か判定などする部分の代わりに出力の処理を書けばいい。
2234 Matches Game
石取りゲームの勝者を答える問題。山は複数あって、一つの山からならば好きな数だけ石を取れる。最後の石を取った人が勝ち。
2209 The King
数列a[i]とnが与えられるので、Σb[i]^nが最大になるa[i]の部分列を選んで最大値を求める問題。ぐ、greedyで……
2240 Arbitrage
為替のレートが与えられるので裁定取引ができるか判定する問題。深さ優先探索で買ってく。
1583 Choose Your Words Carefully
与えられた文章のうち最も出現数の多い単語を調べる問題。
1581 A Contesting Decision
ICPC形式のコンテストの優勝チームとその正解数、ペナルティを求める問題。vector使ったけど通った。
1576 Colorville
すごろくのシミュレートをする問題。
1455 Crazy tea party
長さnの円順列を隣接する要素を入れ替える操作を繰り返して逆順にしたい。必要な操作の最低回数を求めよという問題。greedyでおk.
1572 Automatic Editing
テキストの置換をできる限り繰り返せという問題。一回置換するとまた検索は最初からになる。
1548 Robots
24x24のグリッドのいくつかのセルにゴミが落ちている。右または下に進めるゴミ拾いロボットを0,0からスタートさせて全てのゴミを拾うのに必要なロボットの台数を求める問題。greedy!
2282 Eeny Meeny Moo
ヨセフス数。n≦150なのでm=1から全部シミュレートして間に合う。
2370 Democracy in danger
アメリカ大統領選みたいな選挙で可決に必要な最低得票数を求める問題。greedyでおk.
2346 Lucky tickets
2*n桁(n≦5)の整数のうち前半n桁と後半n桁の和が等しいものの数を求める問題。最初に0があってもいい(00とか)。力技で全列挙してみたら通った……


286問。何とか明後日には300行きそう。ギリギリ……

2240 Arbitrage

bool rec(int c,int s)
{
	//戻ってきたときに通貨が増えてたら裁定
	if(c==s&&p[s]>1)return 1;
	
	//元手から買えるその通貨の量が更新できるなら買う
	rep(i,n)if(p[i]<p[c]*w[c][i])
	{
		p[i]=p[c]*w[c][i];
		if(rec(i,s))return 1;
	}
	return 0;
}

int main()
{
	int cs=0;
	while(cin>>n,n)
	{
		map<string,int> M;
		string str,str2; int t=0;
		rep(i,n)
		{
			cin>>str,M[str]=t++;
			fill(w[i],w[i]+n,0);
		}
		
		cin>>t;
		rep(i,t)
		{
			double a;
			cin>>str>>a>>str2;
			
			w[M[str]][M[str2]]=a;
		}
		
		bool f=0;
		rep(i,n)
		{
			fill(p,p+n,0);
			p[i]=1;
			
			if(rec(i,i))
			{
				f=1; break;
			}
		}
		cout<<"Case "<<++cs<<": "<<(f?"Yes":"No")<<endl;
	}
	
	return 0;
}

制限時間結構ギリギリだった(Limitの7割ちょい)んだけど何でだろ。
たったn=30でそんなに時間かかるハズは……

1581 A Contesting Decision

int main()
{
	int n; cin>>n;
	vector<string> nm(n);
	pair<pi,int> sc[n];
	rep(i,n)
	{
		string b; cin>>b;
		nm[i]=b;
		
		int solve=0,penalty=0;
		rep(j,4)
		{
			int s,t; cin>>s>>t;
			if(t)solve--,penalty+=t+20*(s-1);
		}
		sc[i]=mp(mp(solve,penalty),i);
	}
	sort(sc,sc+n);
	
	cout<<nm[sc[0].second]<<" "<<-sc[0].first.first<<" "<<sc[0].first.second<<endl;
	
	return 0;
}

本当はソートは不要なのだけれど……
max_elementにすればよかったかな。どうでもいいか。

1572 Automatic Editing

bool rpl(string &s,string &f,string &t)
{
	int p=s.find(f);
	if(p==s.npos)return 0;
	
	s=s.substr(0,p)+t+s.substr(p+f.size());
	return 1;
}

int main()
{
	int n;
	while(cin>>n,n)
	{
		cin.ignore();
		string b[n],a[n],str;
		
		rep(i,n)getline(cin,b[i]),getline(cin,a[i]);
		getline(cin,str);
		
		rep(i,n)
		{
			while(rpl(str,b[i],a[i]));
		}
		cout<<str<<endl;
	}
	return 0;
}

stringの扱い(substrとか)にも段々慣れてきたような?(遅

2346 Lucky tickets

int main()
{
	int n; cin>>n;
	n/=2;
	
	int pw[6]; pw[0]=1; rep(i,5)pw[i+1]=pw[i]*10;
	int c[n*9+1]; fill(c,c+n*9+1,0);
	rep(i,pw[n])
	{
		int s=0;
		for(int t=i;t;t/=10)s+=t%10;
		c[s]++;
	}
	
	cout<<inner_product(c,c+(n*9+1),c,0)<<endl;
	return 0;
}

inner_productしたかっただけ。