Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2010-11-01SRM486 Div1

SRM486 Div1 300 OneRegister

| 01:44 | SRM486 Div1 300 OneRegister - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM486 Div1 300 OneRegister - SRM diary(Sigmar) SRM486 Div1 300 OneRegister - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

何か頭が回らない・・・

とりあえず全操作を試してみよう

・・・

tは0にはならないし、一度0になったらそれ以外の値にはなれないので、-は使わない

値がいくつでも/を使うと1になるので、/は最初の1回しか使わない

+は2倍、*は2乗を意味するので、単調増加にしかならない

+の場合でも30回くらいで10億に到達するはずなので単純な探索で行ける

ということは、最初に/する場合としない場合でそれぞれBFSすれば良いか

→とりあえず書く

→/した場合としなかった場合の結果比較が結構面倒・・・

→できた

→サンプル合った

→提出


チャレンジフェーズ

オーバーフロー狙い・・・

→intの人いた!

→失敗

→何と・・・最大値を割り算して判定することでオーバーフローを避けている・・やられた


システムテスト

Passed


ソースコード

あとで考えたら、辞書順にBFSしているので最初に/するのを特別扱いする必要がなかった・・・

class OneRegister {
public:
	string calc(ll s, ll t) {
		queue <ll> q;
		ll qt, qe;
		map <ll, string> val;
		q.push(s);
		val[s]="";
		while(!q.empty()) {
			qt=q.front(); q.pop();
			qe=qt*qt;
			if(qe<=t && !val.count(qe)) {
				val[qe]=val[qt]+"*";
				if(qe==t) return val[qe];
				q.push(qe);
			}
			qe=qt+qt;
			if(qe<=t && !val.count(qe)) {
				val[qe]=val[qt]+"+";
				if(qe==t) return val[qe];
				q.push(qe);
			}
		}

		return "?";
	}

	string getProgram(int s, int t) {
		string res;
		if(s==t) return "";

		res=calc(s, t);//余分な行が混じっていた
		string res1=calc(s, t);
		string res2=calc(1, t);
		if(t==1) res2="/";
		else if(res2!="?") res2="/"+res2;

		if(res1=="?") res=res2;
		else if(res2=="?") res=res1;
		else {
			if(res1.size()<res2.size()) res=res1;
			else if(res1.size()>res2.size()) res=res2;
			else if(res1<res2) res=res1;
			else res=res2;
		}
		if(res=="?") res=":-(";

		return res;
	}
};

SRM486 Div1 450 QuickSort

| 01:44 | SRM486 Div1 450 QuickSort - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM486 Div1 450 QuickSort - SRM diary(Sigmar) SRM486 Div1 450 QuickSort - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

DPっぽい?

2^50か・・・無理だなぁ

期待値の問題によくある線形性バンザイな感じだろうか

うーんすごく場合分けが多そうで難しそうなんだが・・

やっぱりDPで解けるんじゃないのか実は

整列済の状態を基準に考えると、1回の分割により、一定の連続した区間が選ばれることが分かる

ということは状態数は実は50*49/2しかない

じゃあ、整列済みのインデックスi,jにおいて、各ピボットL[i]に対し、初期状態でL[j]がL[i]の左側にいるか右側にいるかを計

算すればDPできる!

→書く

→サンプル通った

→提出


チャレンジフェーズ

map<vector <int>, double>でメモしている人がいるんだが・・・

ああ、、いいのか、別に。。状態数はどちらにしても1000ちょっとしかないのか。

結局何もできず。


システムテスト

Passed


ソースコード

double memo[52][52];

class QuickSort {
public:
	vector <int> sL, L;
	int isleft[50][50];
	int n;

	double rec(int b, int e) {
		double res=0;

		if(memo[b][e]>=0) return memo[b][e];

		for(int i=b; i<e; i++) {
			int cnt=0;
			for(int j=b; j<i; j++) {
				if(isleft[i][j]) cnt++;
			}
			for(int j=i+1; j<e; j++) {
				if(isleft[j][i]) cnt++;
			}
			res+=(rec(b, i)+rec(i+1, e)+cnt)/(e-b);
		}
		memo[b][e]=res;
		return res;
	}

	double getEval(vector <int> L) {
		double res;
		n=L.size();
		this->L=L;
		sL=L;
		sort(sL.begin(), sL.end());
		for(int i=0; i<52; i++) for(int j=0; j<52; j++) memo[i][j]=-1;
		memset(isleft, 0, sizeof(isleft));
		for(int i=0; i<n; i++) {
			int iidx=0;
			for(int k=0; k<n; k++) {
				if(sL[i]==L[k]) {
					iidx=k;
					break;
				}
			}
			for(int j=0; j<n; j++) {
				if(i==j) continue;
				int jidx=0;
				for(int k=0; k<n; k++) {
					if(sL[j]==L[k]) {
						jidx=k;
						break;
					}
				}
				if(iidx<jidx) isleft[i][j]=1;
			}
		}

		res=rec(0, n);
		return res;
	}
};

SRM486 Div1 1000 BatmanAndRobin

| 01:44 | SRM486 Div1 1000 BatmanAndRobin - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM486 Div1 1000 BatmanAndRobin - SRM diary(Sigmar) SRM486 Div1 1000 BatmanAndRobin - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

さてあと35分もあるし、1000でも見てみるか

ふーむ 凸包の面積を求めるだけじゃないのか、これは・・

あー頂点の分け方が2^50あるのか。。

うーんでも、任意の2点を選んで直線を引けば分けられるのでは・・・・

分けられそうだが・・・

凸包のライブラリがない

以前別の凸包の問題を解いたときにバグって放置してしまっていた

しまった・・・

頂点2分割と凸包計算の部分、complex<double>なら時間内にできなくもなさそうだが・・

うーん誤差死しそうな予感がする。long longで書けるコードなだけに嫌な予感がする。。

やめよう。。

300と450を見直す時間に充てるか。。


システムテスト

いっぱい出してる人がいましたがいっぱい落ちてました


後で

頑張ってライブラリ書きました

ちなみに「アルゴリズムC++」という本の内容を大いに参考にしています

というかほぼそのままで少しだけmodifyしています

この本によると普通に僕でもすぐ思いつく包装アルゴリズムというやつよりはグラハム走査という手法が最悪時間において優れる

ようなのでそちらを採用しました

ちなみに凸包の直線上にある点は全て消去した(つもり・・・)


結果的には頂点が1つしかない場合の例外を忘れてたので、本番で書けても多分通らなかったかな・・


ソースコード

typedef complex <double> pt;
typedef complex <ll> pti;

int ccw(pti a, pti b, pti c) {//ベクトルabとacの角度比較
	pti d1=b-a, d2=c-a;
	ll cp=imag(conj(d1)*(d2));
	if(cp>0) return 1;
	if(cp<0) return -1;
	if((d1.real()*d2.real()<0) || (d1.imag()*d2.imag()<0)) return 1;
	if((d1.real()*d1.real()+d1.imag()*d1.imag())<(d2.real()*d2.real()+d2.imag()*d2.imag())) return -1;
	return 0;
}

struct less_miny_maxx {//最小yのうち最大xを小なりとする
	bool operator()(const pti &a, const pti &b) {
		if(a.imag()<b.imag()) return true;
		if(a.imag()>b.imag()) return false;
		if(a.real()>b.real()) return true;
		return false;
	}
};

struct less_p_a {//ベクトルoaとobの角度比較&長さ比較
	const pti &o;
	less_p_a(const pti &_o): o(_o) {}
	bool operator()(const pti &a, const pti &b) {
		pti oa=a-o, ob=b-o;
		ll cp=imag(conj(oa)*(ob));
		if(cp>0) return true;
		if(cp<0) return false;
		ll da=oa.real()*oa.real()+oa.imag()*oa.imag();
		ll db=ob.real()*ob.real()+ob.imag()*ob.imag();
		if(da>db) return true;
		return false;
	}
};

vector <pti> graham_scan(vector <pti> vp) {//グラハム走査
	if(vp.size()<=1) return vp;
	swap(vp[0], *min_element(vp.begin(), vp.end(), less_miny_maxx()));
	sort(vp.begin()+1, vp.end(), less_p_a(vp[0]));
	vp.push_back(vp[0]);
	int m=2;
	for(int i=3; i<(int)vp.size(); i++) {
		while(m>0 && ccw(vp[m], vp[m-1], vp[i])>0) m--;
		m++; swap(vp[i], vp[m]);
	}
	vp.erase(vp.begin()+m, vp.end());
	return vp;
}

double triangle_area_s(pti a, pti b, pti c) {//三角形の面積(符号あり)
	return imag(conj(b-a)*(c-a))*0.5;
}

double polygon_area(vector <pti> vp) {//多角形の面積
	double res=0;
	int n=vp.size();
	if(n<=2) return 0;
	for(int i=1; i<n-1; i++) res+=triangle_area_s(vp[0], vp[i], vp[i+1]);
	return fabs(res);
}

double convex_hull_area(vector <pti> vp) {//凸包の面積
	return polygon_area(graham_scan(vp));
}

class BatmanAndRobin {
public:
	double minArea(vector <int> x, vector <int> y) {
		double res=1e100;
		vector <pti> vp;
		int n=x.size();

		if(n==1) return 0;

		for(int i=0; i<n; i++) vp.push_back(pti(x[i], y[i]));

		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				if(i==j) continue;
				vector <pti> vp1, vp2;
				if(i<j) {
					vp1.push_back(vp[i]);
					vp2.push_back(vp[j]);
				} else {
					vp1.push_back(vp[j]);
					vp2.push_back(vp[i]);
				}
				bool ok=true;
				for(int k=0; k<n; k++) {
					if(k==i || k==j) continue;
					else {
						ll cp=imag(conj(vp[j]-vp[i])*(vp[k]-vp[i]));
						if(cp==0) {
							ll minx=min(vp[i].real(), vp[j].real()), maxx=max(vp

[i].real(), vp[j].real());
							ll miny=min(vp[i].imag(), vp[j].imag()), maxy=max(vp

[i].imag(), vp[j].imag());
							if(minx<=vp[k].real() && vp[k].real()<=maxx && miny<=vp

[k].imag() && vp[k].imag()<=maxy) ok=false;
							if(abs(vp1[0].real()-vp[k].real())<abs(vp2[0].real()-vp

[k].real()) || abs(vp1[0].imag()-vp[k].imag())<abs(vp2[0].imag()-vp[k].imag())) vp1.push_back(vp[k]);
							else vp2.push_back(vp[k]);
						} else {
							if(cp>0) vp1.push_back(vp[k]);
							if(cp<0) vp2.push_back(vp[k]);
						}
					}
				}
				if(!ok) continue;
				res=min(res, max(convex_hull_area(vp1), convex_hull_area(vp2)));
			}
		}

		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20101101