Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-05-23SRM504.5 Div1

SRM504.5 Div1 250 TheNumbersWithLuckyLastDigit

| 23:21 | SRM504.5 Div1 250 TheNumbersWithLuckyLastDigit - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM504.5 Div1 250 TheNumbersWithLuckyLastDigit - SRM diary(Sigmar) SRM504.5 Div1 250 TheNumbersWithLuckyLastDigit - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

とりあえず下1桁だけ考えればよいことは分かった

ここで4の数と7の数でイテレートすればすぐ終わったんだけど、何を思ったかDFSを始めてしまった

しかもうまく書けなくてえらく時間がかかる

何とか15分くらいで書いて提出

幸先悪い・・・


ソースコード

最初に書いたいけてないもの

class TheNumbersWithLuckyLastDigit {
public:
	int min47[200];
	void dfs(int val, int d) {
		if(d==25) return;
		if(val!=0) {
			if(min47[val]>-1) min47[val]=min(min47[val], d);
			else min47[val]=d;
		}
		dfs(val+4, d+1);
		dfs(val+7, d+1);
	}

	int find(int n) {
		int res=1000000000;

		memset(min47, -1, sizeof(min47));
		dfs(0, 0);

		int v=n%10;
		for(int i=1; i<200; i++) {
			if(v==i%10 && n>=i && min47[i]!=-1) res=min(res, min47[i]);
		}
		if(res==1000000000) res=-1;
		return res;
	}
};

後で修正したもの

class TheNumbersWithLuckyLastDigit {
public:
	int find(int n) {
		int res=INF;

		for(int i=0; i<30; i++) {
			for(int j=0; j<30; j++) {
				if(i==0 && j==0) continue;
				if(n>=4*i+7*j && n%10==(4*i+7*j)%10) res=min(res, i+j);
			}
		}
		if(res==INF) res=-1;
		return res;
	}
};

SRM504.5 Div1 550 TheJackpotDivOne

| 23:21 | SRM504.5 Div1 550 TheJackpotDivOne - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM504.5 Div1 550 TheJackpotDivOne - SRM diary(Sigmar) SRM504.5 Div1 550 TheJackpotDivOne - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

サンプルの最後に答えが書いてあるように見えるんだけど・・気のせいかな・・

(最終的に全員同じ金になる)

ストレートフォワードに考えれば、全員同じ金になるまでシミュレーションして、その後は残り金を一気に分配で計算できるだろうが・・・

いくらなんでも簡単すぎ。そんなのが550であるはずがない(←あるはずがあった)

まあでも他に思いつかないしとりあえずやってみよう

できた

サンプル合うなあ・・計算時間も問題ない

最大ランダムケース投入

TLEする

デバッグしてみる

オーバーフローしとる

何それ・・・Javaの人有利じゃん・・・

しかしそもそもBigIntegerを使ったとしてもこの方針で最大ランダムケースが時間内に終わるのだろうか

手元にある遅い多倍長ライブラリで試してみよう

答え合わない

意外と使ってないライブラリの適用にすごく時間がかかる。ライブラリのインタフェースが非常にいけてなかった

時間かかったが、できた

最大ランダムケース問題ない

時間なくなってしまったしこれでとりあえず出すか・・

提出

さて・・

本当にランダムで最大ケースになるのか

・・・

・・・

ならない

最大は、{{1,1,1,...,1,1,10^18}, 10^15}ぐらいのようである

試してみる→TLE

終わった・・・・・・

チャレンジでも頑張ろう


チャレンジフェーズ

ということで多倍長演算をしている人に先程の最大ケースを投げてみる

4失敗

終わった・・・なぜだろう・・


後で

自分の持ってる多倍長ライブラリがあまりにも遅すぎるだけだった

本来進むべき解法は、各moneyをそれぞれ人数で割って商と余りを求めておくことだった

何か色々横道にそれているうちに真っ当な解から外れてしまったな・・・

計算量もちゃんと見積もっておくべきだった。

今回の最大ケースは、1回の分配で( (最大の人の金)-(最小の人の金) )/人数(=47)くらいのお金が配当されるので、47回で最大と最小の差が46/47くらいになると考えれば良い

従って47*log_(47/46) 10^18=約10万くらいなので計算量は楽勝である。うーん・・・


ソースコード

以下は多倍長を使わずにできるよう修正したもの

class TheJackpotDivOne {
public:
	vector<long long> find(vector<long long> money, long long jackpot) {
		vector<long long> res;
		int n=money.size();
		ll maxv=*max_element(money.begin(), money.end());
		ll ave[52], rem[52];
		ll totave=0, totrem=0;
		for(int i=0; i<n; i++) {
			ave[i]=money[i]/n;
			totave+=ave[i];
			rem[i]=money[i]%n;
			totrem+=rem[i];
		}

		while(1) {
			ll d=totave+totrem/n+1;
			vector <ll>::iterator vi=min_element(money.begin(), money.end());
			int idx=vi-money.begin();
			if(money[idx]>=maxv) break;
			d-=money[idx];
			d=min(d, jackpot);
			ll moneyt=money[idx]+d;
			ll avet=moneyt/n;
			ll remt=moneyt%n;
			totave+=avet-ave[idx];
			totrem+=remt-rem[idx];
			money[idx]=moneyt;
			ave[idx]=avet;
			rem[idx]=remt;
			jackpot-=d;
			if(jackpot==0) break;
		}
		sort(money.begin(), money.end());
		for(int i=0; i<n; i++) money[i]+=jackpot/n;
		for(int i=0; i<jackpot%n; i++) money[i]++;
		sort(money.begin(), money.end());
		return money;
	}
};

SRM504.5 Div1 900 TheTicketsDivOne

| 23:21 | SRM504.5 Div1 900 TheTicketsDivOne - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM504.5 Div1 900 TheTicketsDivOne - SRM diary(Sigmar) SRM504.5 Div1 900 TheTicketsDivOne - SRM diary(Sigmar) のブックマークコメント

Problem Statement

後で

見たところ、無限にDPを繰り返せば答えが出るタイプのよくあるやつにしか見えない

実際には無限に繰り返さず適当に打ち切っても精度的には問題ない

漸化式さえできれば、書くだけ

これこそ550くらいが適正じゃないのか・・・

今度から900が出たら問題くらいは読もう・・・


ソースコード

class TheTicketsDivOne {
public:
	double find(int n, int m) {
		double res;

		memset(dp, 0, sizeof(dp));
		dp[0][1][0]=1;

		for(int turn=0; turn<200; turn++) {
			int cur=turn%2, next=(turn+1)%2;
			memset(dp[next], 0, sizeof(dp[next]));
			for(int cnum=1; cnum<=n; cnum++) {
				dp[next][cnum][0]+=1/6.;
				for(int cidx=0; cidx<cnum; cidx++) {
					dp[next][cnum][(cidx+1)%cnum]+=dp[cur][cnum][cidx]/2.;
					dp[next][cnum+1][cidx+1]+=dp[cur][cnum][cidx]/3.;
				}
			}
			dp[next][1][0]=1;
		}

		res=dp[0][n][m-1];
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110523