Hatena::Grouptopcoder

人生是睡眠 - 夢の中ではredcoder -

2010-11-23

SRM 488 Div1 250 TheBoredomDiveOne

10:47

しばらく離れていたが、久しぶりに練習してみた。EclipseCoderを初めて導入してみた。なかなか素敵。(前はFileEditとかをつかっていた。)

preタグで囲むとmapをインクルードしている行が消えてしまうのはなぜだろう。

↑super pre記法があることに今気づいたw 色付けもされていい感じ

DPは苦手なので再起+メモ化でやりました。

pointというint,intのペア型をtypedefしています。

#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <map>
using namespace std;
typedef pair<int,int> point;

#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

map<point,double> memo;

class TheBoredomDivOne {
public:
	double f(int n, int m){
		if(memo[point(n,m)])
			return memo[point(n,m)];
		if(m <= 0){
			return 0;
		}else{
			double val = n*(n -1) + 2*n*m + m*(m-1) +2*n*m*f(n+1,m-1) + m*(m-1)*f(n+2,m-2);
			val = val / (double)((n+m)*(n+m-1)-n*(n-1));
			memo[point(n,m)] = val;
			return val;
		}
	}
	double find(int n, int m) {
		memo = map<point,double>();
		return  f(n,m);
	}
};

2010-06-18

SRM 473 Div2

18:18

なんか最近Code jam をround1で敗退したりしてスランプだったので、topcoderのアカウントを

取り直して心機一転することにした。

すると登録直後はレーティングがあがりやすいので、すぐにDiv1に浮上しました(笑)

次回初Div1がんばります!

Class Name Method Name Difficulty Coding Time Status Points
OnTheFarmDivTwo animals Level One 0:09:43.162 Passed System Test 224.84
SequenceOfCommands whatHappens Level Two 0:11:57.970 Passed System Test 428.98
ChildlessNumbers howMany Level Three 0:52:30.346 Opened 0.00

Rating : 1373

rng_58rng_582010/06/18 20:55アカウント取り直しはルール違反です…

wolf125wolf1252010/06/18 22:09You are allowed to register with our Web site only once and you must provide true and accurate registration information.

本当ですね・・
言語を変えたりしてたので気分を変えようと思ったのですが・・orz
どうしよう・・

wolf125wolf1252010/06/18 23:10今コンタクトフォームから、「ルールを知らずにアカウントを二つ作ってしまったので、どっちかを消すか統合するかしてくれませんか」と送っておきました・・
どうなるんでしょうか・・

2010-05-26

おいおい、なんで調子がいい時に限ってサーバートラブルなんですか?

01:13

Div2 500の提出できなかったコードでもはっておくか・・しくしく

この問題ですが、

「曲Aの次に曲Bが演奏できるならばA->Bに辺をひく」という事を行うと有向グラフになります。

(A->Aといった自己ループも有り。下のソースコードでは隣接行列でグラフを表現しています。)

そうすると、問題は以下になります。

「ノード数Nの有向グラフ上にK個の点を通るパスは何通り作れるか?」

解き方としては、Kに関するDPでやります。

各点について、各ノードを終点とするk (1 <= k <= K)点を通るパスの数(=score)を考えます。

k = 1の時は、scoreは全て1です。

k+1 の時は、 各スコアはそのノードを指している全てのノードの kの時のスコアの合計

になります。

最後はscoreの全部の要素を合計してやれば答えがでます。

ちゃんとしたDPの問題を時間内に解けたのはひさしぶりだったのに・・提出できずに悔しいです。

(注 : ll は long long の事です)

class EllysPlaylists {
public:
  int countPlaylists(vector <string> songs, int K) {
    int result = 0;
    int n = songs.size();
    if(K == 1){
    	return n;
    }
    vector<vector<bool> > g(n, vector<bool>(n,0));
    for(int i = 0; i < n; i++){
    	for(int j = 0; j < n; j++){
    		if(songs[j].substr(songs[j].length()-3,3) == songs[i].substr(0,3)){
    			g[i][j] = true;
    		}
    	}
    }
    vector<ll> score(n,1);
    for(int k = 1; k < K; k++){
    	vector<ll> next(n,0);
    	for(int i = 0; i < n; i++){
    		for(int j = 0; j < n; j++){
    			if(g[j][i]){
    				next[i] += score[j] % 1000000007;
    			}
    		}
    	}
    	score = next;
    }
    for(int i = 0; i < n;i++){
    	result = (result + score[i]) % 1000000007;
    }
    return result;
  }
}

JosieJosie2011/07/09 15:07Finally! This is just what I was loiokng for.

jsqwqszrigjsqwqszrig2011/07/10 00:18gpULQc <a href="http://elmukzbzvoif.com/">elmukzbzvoif</a>

vjgzvkgbtuvjgzvkgbtu2011/07/10 20:59aCeGMx , [url=http://tvcrucqxrhtz.com/]tvcrucqxrhtz[/url], [link=http://gfohhkfjdiwo.com/]gfohhkfjdiwo[/link], http://rmicxwikygqg.com/

affajccaffajcc2011/07/12 21:49HRhtDv , [url=http://iyckeemzwdzv.com/]iyckeemzwdzv[/url], [link=http://qcecytxfpwde.com/]qcecytxfpwde[/link], http://aggzyxuwyxhq.com/

2010-05-10

【復習】Google Code Jam 2009 Round 2-D "Watering Plants"

12:46

去年のRound2のD問題を復習したぞ。本番でLargeが通っている人は64人しかいなかったようだ。

おれなんかround2は0点だったがな(自慢)!

いくら考えてもわからないので、id:wata_orzのコードを読んで理解したつもりになってからC++で書いてみたぞ。

方針としては

まず答えとなる半径をいきなり決めておいて、二分探索で正しい値にもっていく。

円の中心の候補となるのは、半径Rの円が任意の2円に外接するような点。

その中に全部の植物が入っているかどうかチェック。OKなら半径を小さく、NGなら大きくする

O(40 * N^5)という遅いプログラムだがmacbook whiteで4分ぐらいで終わりました。

doubleの比較はepsironを使うとか、初めて二分探索を書いてみたとか、初めて複素数を使ってみたとか

いろいろためになりました・・

#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
#include <algorithm>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
#include <list>
#include <queue>

#define EPS 1e-9

using namespace std;
typedef long long ll;
typedef pair<int,int> point;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
inline ll toLL(string s) {ll v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}</ppp>
//for debug
template<class T> ostream &operator<<(ostream &os, vector<T> v){if(v.empty()){ os << "[]"; return os;} os << "["; for(int i = 0; i < v.size() - 1; i++) os << v[i] << ", "; os << v[v.size() - 1] << "]"; return os; }
template<class T> ostream &operator<<(ostream &os, list<T> l){ os << "["; while(l.size() != 1){ os << l.front() << ", "; l.pop_front(); } os << l.front(); os << "]"; return os; }
template<class T> ostream &operator<<(ostream &os, set<T> s){if(s.empty()){ os << "[]"; return os;} os << "["; while(s.size() != 1){ T o = *s.begin();os << o << ", "; s.erase(o); } os << *s.begin(); os << "]"; return os; }

//二円の交点を返す。同じ円が与えられた場合はその円の中心を返すことにした
vector< complex<double> > getCross(complex<double> c1, double r1, complex<double> c2, double r2){
	vector< complex<double> > res;
	double d = abs(c2-c1);
	if(d < EPS && abs(r2-r1) < EPS){
		//only for this problem
		res.push_back(c1);
	}else if(abs(r2-r1) + EPS < d && d + EPS < r1 + r2){
		complex<double> v0 = ((c2 - c1) / d);
		complex<double> v1 = v0 * complex<double>(0,1);
		double d1 = (r1*r1 - r2*r2 + d*d) / (2 * d);
		double h = sqrt(r1*r1 - d1*d1);
		res.push_back(c1 + d1 * v0 + h * v1);
		res.push_back(c1 + d1 * v0 - h * v1);
	}
	return res;
}

double solve(vector< complex<double> > points, vector<double> radius){
	int n = points.size();
	if(n == 1)
		return radius[0];
	else if(n == 2)
		return max(radius[0],radius[1]);
	double low = 0;
	double high = 10000;
	for(int i = 0; i < n; i++){
		low = max(low,radius[i]);
	}
	double r;
	bool success;
	int count = 40;
	//rを先に決めて二分探索
	while(count--){
		r = (high + low) / 2.0;
		success = false;
		for(int i = 0; i < n; i++){
			for(int j = i; j < n; j++){
				for(int k = i; k < n; k++){
					for(int l = k; l < n; l++){
						//二円の外接円の中心となる候補点
						vector< complex<double> > cross1 = getCross(points[i],r-radius[i],points[j],r-radius[j]);
						vector< complex<double> > cross2 = getCross(points[k],r-radius[k],points[l],r-radius[l]);

						//どちらかの円にすべての植物がふくまれていればOK
						for(int u = 0; u < cross1.size(); u++){
							for(int v = 0; v < cross2.size(); v++){
								for(int w = 0; w < n; w++){
									if(!(abs(points[w] - cross1[u]) + radius[w] < r + EPS || abs(points[w] - cross2[v]) + radius[w] < r + EPS))
										goto NG;
								}
								success = true;
								goto OK;
								NG:
								;
							}
						}
					}
				}
			}
		}
		OK:
		if(success)
			high = r;
		else
			low = r;
	}
	return r;
}

int main(){
	int cases;
	ifstream in;

	//string ifile = "D-small-practice.in";
	string ifile = "D-large-practice.in";
	//string ifile = "D-test.in";

	in.open(ifile.c_str());
	string ofile = ifile.substr(0,ifile.find('.')) + ".out";
	ofstream fout;
	fout.open(ofile.c_str());

	in >> cases;
	for(int c = 0; c < cases; c++){
		int n;
		in >> n;
		vector< complex<double> > points(n);
		vector< double > radius(n);
		for(int i = 0; i< n; i++){
			in >> points[i].real() >> points[i].imag() >> radius[i];
		}

		double ans = solve(points,radius);
		cout << setprecision(15);
		fout << setprecision(15);
		cout << "Case #" << (c + 1) << ": " << ans << endl;
		fout << "Case #" << (c + 1) << ": " << ans << endl;
	}

}

2010-05-09

【結果】 Google Code Jam Qualification Round

19:51

パチョレック!やったよ!全部あってたよ!

http://www.go-hero.net/jam/10/name/kopemon

ワニステーキでお祝いだ!

(美味しそうと思った人は是非、はてなスターで表現しましょう)

f:id:wolf125:20100509195315j:image