Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-05-23SRM504.5 Div1

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;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110523