SRM diary(Sigmar)

SRM510 Div1 500 TheLuckyGameDivOne

SRM510, Div1 | 20:47 |

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