PKU演習問メモ（2010/3/24）

PKU

解説必要な問題はなし（ｷﾘｯだとブログの意味がないので一応今日解いた問題とその方針だけメモ……

1111 Image Perimeters
How many islands?系の問題。地形の周長を求める。周囲4マスに'X'がない→周長に1プラス。周囲8マスの'X'について再帰。
1132 Border
壁を右手にさわりながら移動したときの壁の形を書く。移動方向とそれにより決まる壁の座標の関係が一意に定まるのでそれを書く。
1164 The Castle
How many islands?系の問題。地図の代わりにその地点での四方の壁の情報が与えられている。
1247 Magnificent Meatballs
要素数n（n<=30）の配列aについてΣ[k=1,i]ak==1/2Σ[i+1,n]akなるiを求める問題。
1273 Drainage Ditches
ditchは溝という意味らしいｗ排水溝に流せる水量を最大流アルゴリズムにより求める。Edmond-Karpのアルゴリズムでおｋだが、inputに同じエッジが二本以上あるテストケースがあるようで注意を要する。
1330 Nearest Common Ancestors
木の共通祖先を求める問題。ノードの0番が根な訳ではない。
1411 Calling Extraterrestrial Intelligence Again
以下のような素数の組p, qを求めよ： pq <= m and a/b <= p/q <= 1を満たし、そのようなp,qの中で積pqが最大となるもの。だそうで。エラトステネスで生成する素数の範囲に気をつけないとWAる。
1664 放苹果
苹果とは中国語でりんごのことを言うらしい。区別のないm個のりんごを区別のないn枚の皿に載せる組み合わせを求めよ。空の皿があってもよい。再帰で計算するのが自然？m,n≦10と小さいのでメモ化も不要。
1862 Stripes
それぞれの体重がw[i]の虫がいる。体重w[i]とw[j]の２匹の虫が融合すると2*sqrt(w[i]*w[j])の一体の虫になる。全ての虫が融合したときにありうる最小の体重を求めるという問題。はじめに融合する→√がいっぱいつく→小さくなる。よってgreedyでおｋ．
2238 Guessing Game
数当てゲームのシミュレート。シミュレートすればおｋ.
2339 Rock, Scissors, Paper
題意の通りじゃんけん+シミュレーションを実装すればおｋ.
2470 Ambiguous permutations
位数が3以上の巡回群が存在するか判定する（で言葉の使い方あってるのか？）
2478 Farey Sequence
a＜b≦nかつgcd(a,b)=1なる自然数a,bの組を求める問題。Eulerのphi関数を使う。
2497 Strategies
やや面倒な実装問。みんなコードやたら短いな……
2507 Crossed ladders
ああなんか方針メモが凄く適当になってきてる。通路に二つのはしご（それぞれ長さx,y）が左向きと右向きに傾いてかけてあり、それが地面からcの高さで交わっている。通路の幅を求めよ。幅wを含む等式が立てられるのでそれを満たすようなwを二分法により求めればよい。
2526 Center of symmetry
n個の点の「中心」が存在するか否かを判定する問題。中心の候補はΣp/nただ一つであり、n個の点に対してそれに対称な点があるか調べればよい。1万の二乗が少し不安だったのでbinary_searchを使用。
2533 Longest Ordered Subsequence
数列の部分集合で増加列になっているもののうち最長の長さを求める問題。動的計画法によるO(n^2)の解法で通る。
2538 WERTYU
文字をキーボードで左に一つずらした文字に変換する問題。そのまま実装。
2656 Unhappy Jinjin
簡単な実装。
3589 Number-guessing Game
いわゆるhit&blow.


これで231問。
hit&blowのコードでも貼っておこう。

int main()
{
	int t; cin>>t;
	rep(T,t)
	{
		string a,b;
		cin>>a>>b;
		
		string c=a+b;
		sort(all(c)); c.erase(unique(all(c)),c.end());
		
		int hb=a.size()+b.size()-c.size(),h=0;
		rp(i,a)if(a[i]==b[i])h++;
		
		cout<<h<<"A"<<hb-h<<"B"<<endl;
	}
	return 0;
}

TopCoderの上位陣のSTLの使い方をまねて、最近はSTLを使うことが多くなった。
PKUでやるとTLEに陥ったりするけどｗ