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;
	}
};

SRM510 Div1 500 TheLuckyGameDivOne

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

Problem Statement

コーディングフェーズ

そもそもJohnがminimize、Brusがmaximizeするのかと勘違いしていた

答え合わなくて終了

いい加減ちゃんと問題を読むようにしないと・・・


後で

まずは、ラッキーナンバーが2^11程度しかないので、それを全部列挙すること

あとは適当に全探索したらOK

・・・なんだけど、この全探索が曲者でとても難しい


手始めに、ラッキーナンバー数をnとすると、解を1~nで探索する

解がiだとすると、全てのbLenで解がi以上となるjLenが存在するか判定できればOK

全てのbLenで解がi以上となるとはどういうことだろうか

ラッキーナンバーが以下のような数直線で並んでいたとする(*がラッキーナンバー)

---*-----*----------*----*-----*----

例えば、解が3になるためには、bLenが以下のような範囲以上である必要がある

--[*-----*----------*---]*-----*----

同様に、bLenは以下のような範囲以上である必要がある

---*----[*----------*----*----]*----

この時点で、どちらの範囲もbLen以上だったとすると、この5つのラッキーナンバーの内側では全てのbLenで解がi以上となる区間ということができる。

(実際には左端や右端はbLenの長さによってある程度はみ出せるため、もう少し広い範囲でOK)

この範囲内にjLenを置くことができれば、解がi以上となりうると言える。


このような複雑な判定をすることで答えが求められるが・・・ちょっと大変すぎなような

もっと簡単に出せないかなぁ。。。


ソースコード

意外と短いです

class TheLuckyGameDivOne {
public:
	int find(long long a, long long b, long long jLen, long long bLen) {
		int res=0;

		vector <ll> cand;
		queue <ll> q;
		q.push(0);
		while(!q.empty()) {
			ll num=q.front(); q.pop();
			if(num>=a) cand.push_back(num);
			if(num*10+4<=b) q.push(num*10+4);
			if(num*10+7<=b) q.push(num*10+7);
		}

		int n=cand.size();
		for(int i=1; i<=n; i++) {
			int cur=0;
			while(cur+i<=n) {
				int begin=cur;
				while(cur+i<n) {
					if(cand[cur+i]-cand[cur]>bLen) break;
					cur++;
				}
				ll l=max(a, cand[begin+i-1]-bLen+1), r=min(b, cand[cur]+bLen-1);
				if(r-l+1>=jLen) res=i;
				cur++;
			}
		}
		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110622