Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-01-11Facebook Hacker Cup 2011 Qual Round

Facebook Hacker Cup 2011 Qual Round DoubleSquares

| 22:59 | Facebook Hacker Cup 2011 Qual Round DoubleSquares - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Facebook Hacker Cup 2011 Qual Round DoubleSquares - SRM diary(Sigmar) Facebook Hacker Cup 2011 Qual Round DoubleSquares - SRM diary(Sigmar) のブックマークコメント

Problem Statement

数Xが与えられるので、平方数2つの和で表す方法が何通りあるか答える

0<=X<=約20億


解答方針

0~X/2までの平方数(sqとする)を列挙する

平方根をイテレートして列挙すると0~3万くらいで0~10億まで列挙可能なのですぐ終わる

X-sqが平方数かどうか確認して、平方数なら解を+1する

非常にストレートフォワードな問題・・・


ソースコード

vector <int> sq;
int n;

int solve(int x) {
	int res=0;
	for(int i=0; i<n && sq[i]<=x/2; i++) {
		int j=x-sq[i];
		int rt=(int)floor(sqrt((double)j));
		if(rt*rt==j) res++;
	}
	return res;
}

int main() {
	//ifstream fin("input.txt", ios::in);
	ofstream fout("output.txt", ios::out);
	FILE *fpin=fopen("input.txt", "r");
	//FILE *fpout=fopen("output.txt", "w");
	
	for(int i=0; i*i<=2147483647/2; i++) {
		sq.push_back(i*i);
	}
	n=sq.size();

	int N;
	fscanf(fpin, "%d", &N);
	for(int i=0; i<N; i++) {
		int X;
		fscanf(fpin, "%d", &X);
		fout << solve(X) << endl;
	}
}

Facebook Hacker Cup 2011 Qual Round PegGame

| 22:59 | Facebook Hacker Cup 2011 Qual Round PegGame - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Facebook Hacker Cup 2011 Qual Round PegGame - SRM diary(Sigmar) Facebook Hacker Cup 2011 Qual Round PegGame - SRM diary(Sigmar) のブックマークコメント

Problem Statement

パチンコみたいな台が与えられる

市松模様的に障害物があるが一部障害物のない部分が入力で与えられる

一番上の任意の場所から玉を落とし、障害物に当たると、左端と右端以外は1:1の確率で右か左に跳ねる

一番下のどこかに目的地が与えられるので、その位置に行く確率が最も高い入り口及びその確率を答える


解答方針

各入口から落とした場合について、行き先候補の確率をDPで計算する

シンプルなDP。やるだけ。

tieはないという注意書きがあったがサンプルにtieがあったような気がするのは気のせいだろうか


ソースコード

デバッグしやすいようにvector <string>で台を表現しています

(VC++だとvector <string>が図としては見やすい)

pair <int, double> solve(int R, int C, int K, vector <string> &game) {
	pair <int, double> res(0, 0.);

	for(int i=0; i<C-1; i++) {
		double dp[205][205];
		memset(dp, 0, sizeof(dp));
		dp[0][i*2+1]=1;
		for(int j=0; j<R-1; j++) {
			for(int k=1; k<C*2-2; k++) {
				if(game[j][k]=='x') continue;
				if(game[j+1][k]=='.') dp[j+1][k]+=dp[j][k];
				else if(game[j+1][k-1]=='x') dp[j+1][k+1]+=dp[j][k];
				else if(game[j+1][k+1]=='x') dp[j+1][k-1]+=dp[j][k];
				else {
					dp[j+1][k-1]+=dp[j][k]*0.5;
					dp[j+1][k+1]+=dp[j][k]*0.5;
				}
			}
		}
		if(dp[R-1][K*2+1]>res.second) {
			res.first=i;
			res.second=dp[R-1][K*2+1];
		}
	}

	return res;
}

int main() {
	//ifstream fin("input.txt", ios::in);
	ofstream fout("output.txt", ios::out);
	FILE *fpin=fopen("input.txt", "r");
	//FILE *fpout=fopen("output.txt", "w");
	
	int N;
	fscanf(fpin, "%d", &N);
	for(int i=0; i<N; i++) {
		int R, C, K, M;
		fscanf(fpin, "%d%d%d%d", &R, &C, &K, &M);
		vector <int> r(M), c(M);
		for(int j=0; j<M; j++) {
			fscanf(fpin, "%d%d", &r[j], &c[j]);
		}
		vector <string> game(R, string(C*2-1, 'x'));
		for(int j=0; j<R; j++) {
			for(int k=1; k<C*2-2; k++) {
				if((j%2)^(k%2)) game[j][k]='.';
			}
		}
		for(int j=0; j<M; j++) {
			if(r[j]%2==0) game[r[j]][c[j]*2]='.';
			else game[r[j]][c[j]*2+1]='.';
		}
		pair <int, double> res=solve(R, C, K, game);
		fout << res.first << " " << fixed << setprecision(6) << res.second << endl;
	}
}

Facebook Hacker Cup 2011 Qual Round StudiousStudent

| 22:59 | Facebook Hacker Cup 2011 Qual Round StudiousStudent - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Facebook Hacker Cup 2011 Qual Round StudiousStudent - SRM diary(Sigmar) Facebook Hacker Cup 2011 Qual Round StudiousStudent - SRM diary(Sigmar) のブックマークコメント

Problem Statement

1~9個の長さ最大10の単語が与えられるので、適当に順番を並び替えて全て連結し、辞書順で最も早い文字列にする


解答方針

数が少ないのでnext_permutationで全探索すれば良いです


・・・と簡単すぎてあまりにあっけないので、時間もあることだしもっと簡単で効率的な方法を考えました。

ある2つの単語aとbを比較した場合、片方がもう一方のprefixでない限り、辞書順に早いほうから並べれば良いのは明らか。

prefixだった場合は・・何となくa+bのほうがb+aより辞書順が早ければaを先に持ってくるべきな気がする。

色々場合分けして考えてみると本当っぽい。

厳密には証明していないが上記の順序付けでソートするだけで良いのでは。

200ケースくらい試したがnext_permutationの解と完全に一致するので多分大丈夫だろう。


ソースコード

bool lesslexi(const string &a, const string &b) {
	return a+b<b+a;
}

int main() {
	//ifstream fin("input.txt", ios::in);
	ofstream fout("output.txt", ios::out);
	FILE *fpin=fopen("input.txt", "r");
	//FILE *fpout=fopen("output.txt", "w");
	
	int N;
	fscanf(fpin, "%d", &N);
	for(int i=0; i<N; i++) {
		int M;
		fscanf(fpin, "%d", &M);
		vector <string> word(M);
		for(int j=0; j<M; j++) {
			char buf[100];
			fscanf(fpin, "%s", buf);
			word[j]=string(buf);
		}
		sort(word.begin(), word.end(), lesslexi);
		string s=accumulate(word.begin(), word.end(), string());
		fout << s << endl;
	}
}
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110111