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