Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2010-09-26SRM483 Div1

SRM483 Div1 250 BestApproximationDiv1

| 21:09 | SRM483 Div1 250 BestApproximationDiv1 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM483 Div1 250 BestApproximationDiv1 - SRM diary(Sigmar) SRM483 Div1 250 BestApproximationDiv1 - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→問題長い・・

→問題が分かりにくいが、0<=A<B<=maxDenの範囲で小さいものから全探索して、最もexact digitが多いもの(同じdigitでは最初に見つかったもの)を探せば良いみたい</ppp>

→小数点以下6桁まで計算しないといけないらしい

→こういう小数点以下を正確に計算する必要がある問題では、散々doubleには痛い目に合わされている

→doubleは表現方法などが実装依存なところがあり、うまくいった試しがない

→ということで、doubleは使わない。A/BをA*1000000/B%1000000とすれば、小数点以下6桁を整数で正確に計算できる(A/Bは1未満なので、今回は%1000000は必要ない)

→書く→string subscript out of range

→A*1000000/Bが6桁未満の数になる場合があるのが問題らしい。6桁になるまで後ろに'0'をpush_backする(←大間違い)

→答えが合わない・・・・・・

→デバッグする

→・・・

→・・・

→あ・・・後ろでなくて前に'0'を埋めないといけない

→アホか・・

→streamのsetwとsetfillを使って'0'を埋める

→サンプル合う

→提出

→170点とか・・・500できないと終わる・・・

→500へ


チャレンジフェーズ

→多分doubleとか使ってる人は大体落ちるんじゃないか

→まあ・・でも落とすケース作るのは結構大変ですよね。無理ですね。

→もしかしたら0<=A<B<=maxDenのところでoff by oneエラーをする人がいるかもしれない</ppp>

→まさかと思ったが本当にいた。B<maxDenになってる。相手が日本人で申し訳ないですが+50</ppp>

システムテスト

→Passed


以下、ソースです。

提出時からちょっと体裁整えてます。

class BestApproximationDiv1 {
public:
	string findFraction(int maxDen, string number) {
		string res;
		number=number.substr(2);
		int maxd=0;
		int A=0, B=0;

		for(int i=1; i<=maxDen; i++) {
			for(int j=0; j<i; j++) {
				int dig=j*1000000/i;
				stringstream ss;
				ss << setw(6) << setfill('0') << dig;
				string s=ss.str();
				//for(int k=s.size(); k<6; k++) s.push_back('0'); ここが間違えてた部分。提出時は残したまま
				int cnt=1;
				for(int k=0; k<6; k++) {
					if(s[k]==number[k]) cnt++;
					else break;
				}
				if(cnt>maxd) {
					maxd=cnt;
					A=j; B=i;
				}
			}
		}

		stringstream ss;
		ss << A << "/" << B << " has " << maxd << " exact digits";
		res=ss.str();
		return res;
	}
};

SRM483 Div1 500 Bribes

| 21:09 | SRM483 Div1 500 Bribes - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM483 Div1 500 Bribes - SRM diary(Sigmar) SRM483 Div1 500 Bribes - SRM diary(Sigmar) のブックマークコメント

Problem Statement

問題を見る

→普通にやれば2^50のDPの問題

→いかにもDPなので計算量を削減できる可能性を考える

→例えば本当に50個も状態を覚える必要があるのか。何しろ隣に行くごとに1/2になる上に余り切り捨てなので・・・

→influenceの最大値は500・・ということは、、512が2^9なので10個以上離れたところの状態は覚える必要がない

→ということで最大2^18(*50)くらいのDPではなかろうか

→d番目のvoterについて、直前18人が買収されたかどうかの状態を記録する。

→d番目から9人前のvoterが、前後18人の買収状況でresistanceが0にならなければ、DPを更新しない。そうでなければ更新する

→うーん・・・でも、結構書くのが面倒そうな感じなんですが・・・本当にこれが答えか・・

→最小カットとか、どうだろ・・

→ダメっぽい。使えない

→うーん・・・

→うーん・・・

→やっぱりDPしかないか。。残り30分になったから書こう

→まず18人以下だと直前18人の状態が覚えられないので全探索で答えを出して・・

→次に18人より多い場合、DPの初期値として最初の18人分の全状態を計算して・・・

DPの本体を書いて、DPの終了値として有効なものを探索して・・・

→できた→18人より多いサンプル3、4が合わない

→いろいろ間違ってる。直す。合わない。

→まだ間違ってる。直す。合わない。

→だめだ・・時間切れ・・・終わった・・・


チャレンジフェーズ

→他の人のは長くて読み解けない。

→何もせず。


システムテスト

→皆さんFailedだらけになりみるみるうちに順位が上がる

→提出時から200位以上も上がった・・こんなこともあるんだな・・


終了後

→500の間違ってるところが3箇所くらいあった。だめだこれは・・

→特にbitmaskの上位と下位の桁がDPの進み方と逆になってたのが大きな設計ミスだった。これのせいで非常に混乱した。

→250も前後を間違えたし、前回もハノイの問題で前後間違えたし前後間違いが最近の鬼門なのか


以下、修正したソースです。

よく考えたら512未満だから前後9人ではなく8人でよかったのでそこは修正しました。

あと、ir5さんの記事を見て思ったけど16人以下の場合の全探索やらDP初期値の計算やら有効な最終解の計算やらの面倒なところは(0,0)の番兵を前後に8人置けば必要なかった気がする。こういうのができるとコーディングがはるかに楽になるので勉強不足を感じる次第です。

int dp[51][1<<16];

class Bribes {
public:
	int minBribes(vector <int> influ, vector <int> resist) {
		int res=1000000000;
		int inff[50][50];
		int n=influ.size();
		int allmask=(1<<16)-1;

		memset(inff, 0, sizeof(inff));
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				inff[i][j]=influ[i]/(1<<abs(i-j));
			}
		}

		//16人以下の場合は全探索
		if(n<=16) {
			for(int mask=0; mask<(1<<n); mask++) {
				bool ok=true;
				for(int i=0; i<n; i++) {
					int sum=0;
					for(int j=0; j<n; j++) {
						if(!(mask&(1<<j))) continue;
						sum+=inff[j][i];
					}
					if(sum<resist[i]) {
						ok=false;
						break;
					}
				}
				if(ok) {
					res=min(res, __builtin_popcount(mask));
				}
			}
			if(res==1000000000) res=-1;
			return res;
		}

		memset(dp, 127, sizeof(dp));
		//DP初期値の計算
		for(int mask=0; mask<(1<<16); mask++) {
			bool ok=true;
			for(int i=0; i<8; i++) {
				int sum=0;
				for(int j=15, k=0; j>=0; j--, k++) {
					if(!(mask&(1<<k))) continue;
					sum+=inff[j][i];
				}
				if(sum<resist[i]) {
					ok=false;
					break;
				}
			}
			if(ok) dp[16][mask]=__builtin_popcount(mask);
		}
		//DP更新
		for(int d=16; d<n; d++) {
			for(int mask=0; mask<(1<<16); mask++) {
				if(dp[d][mask]>=1000000000) continue;
				int sum=0;
				for(int j=0; j<16; j++) {
					if(d-1-j<0) continue;
					if(!(mask&(1<<j))) continue;
					sum+=inff[d-1-j][d-8];
				}
				if(sum+inff[d][d-8]<resist[d-8]) continue;
				int nmask=((mask<<1)&allmask)|1;
				dp[d+1][nmask]=min(dp[d+1][nmask], dp[d][mask]+1);
				nmask=(mask<<1)&allmask; //allmaskと&とってなかったので変な更新してた
				if(sum>=resist[d-8]) 
					dp[d+1][nmask]=min(dp[d+1][nmask], dp[d][mask]);
			}
		}
		//有効な最終解の判定
		for(int mask=0; mask<(1<<16); mask++) {
			if(dp[n][mask]>res) continue;
			bool ok=true;
			for(int i=n-8; i<n; i++) {
				int sum=0;
				for(int j=n-1, k=0; j>=n-16; j--, k++) { //ここが前後間違いの主犯
					if(!(mask&(1<<k))) continue;
					sum+=inff[j][i];
				}
				if(sum<resist[i]) {
					ok=false;
					break;
				}
			}
			if(ok) res=min(res, dp[n][mask]);
		}

		if(res>=1000000000) res=-1; //ここも忘れてたポイント・・・
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20100926