Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2011-06-22SRM510 Div1

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