Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-06-22SRM510 Div1

SRM510 Div1 250 TheAlmostLuckyNumbersDivOne

| 20:47 | SRM510 Div1 250 TheAlmostLuckyNumbersDivOne - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM510 Div1 250 TheAlmostLuckyNumbersDivOne - SRM diary(Sigmar) SRM510 Div1 250 TheAlmostLuckyNumbersDivOne - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

これは・・ほとんど4と7しか出てこないんだったら全探索で良いのでは?

2^16*10*10くらいだよなぁ・・・全然いけそう

さて書くか・・ん???解がlong longだと・・???

そんなばかな・・・どう考えても32bitを超えると思えないが・・

・・・

・・・

メモ化できるようにdfsで書いてみよう(←判断誤りでした。とりあえず全探索コードを書いておけば・・・)

とてつもない場合分けが発生

答え合わない~~

途中ちょっと500に浮気。500難しい。戻ってくる

結局50分くらい経ってようやく答え合った

最大ケースで700万くらい。やっぱりlong longいらんじゃないか!!罠か!!!最初から全探索書いて試せば良かった。

結局メモ化もせず提出。

終わった・・・


チャレンジフェーズ

非常に僅差で並んでいるためリスクが大きいので何もせず


ソースコード

提出したやつ

class TheAlmostLuckyNumbersDivOne {
public:
	//上位桁からDFS
	//d: 桁
	//z: 上位桁に0以外が含まれる
	//a: 上位桁に4と7以外が含まれる
	//t: 下位桁に上限あり(上位桁がexactlyにviとイコール)
	ll rec(vector <int>& vi, int d, int z, int a, int t) {
		if(vi.size()==1 && vi[0]==0) return 0;
		if(d==vi.size()) return 1;

		ll res=0;
		if(!z) {
			res+=rec(vi, d+1, 0, 0, 0);
		}
		if(!t) {
			res+=rec(vi, d+1, 1, a, 0)*2;
			if(!a) {
				if(!z) res+=rec(vi, d+1, 1, 1, 0)*7;
				else res+=rec(vi, d+1, 1, 1, 0)*8;
			}
		} else {
			if(vi[d]==0) {
				if(z && !a) res+=rec(vi, d+1, 1, 1, 1);
			} else if(vi[d]<4) {
				if(!a) {
					if(!z) res+=rec(vi, d+1, 1, 1, 0)*(vi[d]-1);
					else res+=rec(vi, d+1, 1, 1, 0)*vi[d];
					res+=rec(vi, d+1, 1, 1, 1);
				}
			} else if(vi[d]==4) {
				res+=rec(vi, d+1, 1, a, 1);//4
				if(!a) {
					if(!z) res+=rec(vi, d+1, 1, 1, 0)*(vi[d]-1);
					else res+=rec(vi, d+1, 1, 1, 0)*vi[d];
				}
			} else if(vi[d]<7) {
				res+=rec(vi, d+1, 1, a, 0);//4
				if(!a) {
					if(!z) res+=rec(vi, d+1, 1, 1, 0)*(vi[d]-2);
					else res+=rec(vi, d+1, 1, 1, 0)*(vi[d]-1);
					res+=rec(vi, d+1, 1, 1, 1);
				}
			} else if(vi[d]==7) {
				res+=rec(vi, d+1, 1, a, 0);//4
				res+=rec(vi, d+1, 1, a, 1);//7
				if(!a) {
					if(!z) res+=rec(vi, d+1, 1, 1, 0)*(vi[d]-2);
					else res+=rec(vi, d+1, 1, 1, 0)*(vi[d]-1);
				}
			} else {
				res+=rec(vi, d+1, 1, a, 0);//4
				res+=rec(vi, d+1, 1, a, 0);//7
				if(!a) {
					if(!z) res+=rec(vi, d+1, 1, 1, 0)*(vi[d]-3);
					else res+=rec(vi, d+1, 1, 1, 0)*(vi[d]-2);
					res+=rec(vi, d+1, 1, 1, 1);
				}
			}
		}

		return res;
	}

	long long find(long long a, long long b) {
		long long res;

		a--;
		vector <int> aa, bb;
		while(a) {
			aa.push_back(a%10);
			a/=10;
		}
		while(b) {
			bb.push_back(b%10);
			b/=10;
		}
		reverse(aa.begin(), aa.end());
		reverse(bb.begin(), bb.end());
		ll an=rec(aa, 0, 0, 0, 1);
		ll bn=rec(bb, 0, 0, 0, 1);
		res=bn-an;
		return res;
	}
};

プラクティスでは以下みたいな簡単なので通りました

dfsのほうが望ましかったかな・・

class TheAlmostLuckyNumbersDivOne {
public:
	long long find(long long a, long long b) {
		long long res=0;

		queue <pair <ll, int> > q;
		q.push(make_pair(0, 0));
		while(!q.empty()) {
			pair <ll, int> qt=q.front(); q.pop();
			if(qt.first>=a && qt.first<=b) res++;
			for(int i=0; i<10; i++) {
				ll nval=qt.first*10+i;
				if(nval==0 || nval>b) continue;
				if(i==4 || i==7) q.push(make_pair(nval, qt.second));
				else if(qt.second==0) q.push(make_pair(nval, 1));
			}
		}

		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110622