SRM510 Div2 Medium - TheLuckyGameDivTwo

問題

全ての桁が4か7の数字をLuckyNumberと呼ぶ
区間[a,b]からまずJohn君が長さalの区間Sを取り出し、次にBrus君がSから長さblの区間Tを取る
Tに含まれるLuckyNumberの個数をゲームのスコアとする
John君はスコアを最大化、Brus君は最小化しようとするときスコアは何点になるか

解法

John君がある区間を選んだとき、そこからBrus君は長さblの区間でLuckyNumberが一番少ない区間を選ぶ
ということはJohn君はどこを選んでもLuckyNumberがなるべく多いような区間を取るべき
つまり最小値の最大値を求めればいい
John君の区間Sを全探索し、それぞれについてBrus君の区間Tを全て試してそれらの最小値を求める
それらの最小値の最大値が答えになる

実装

累積和をとって、ある区間に含まれるLuckyNumberの個数をO(1)で求められるようにしておく
(累積和かしゃくとり法のどっちかは使わないとb-a=4444, al=2222, bl=1111なんかが怪しい)

class TheLuckyGameDivTwo {
	public:
	int find(int a, int b, int al, int bl) {
		int k[5050] = {};
		reps(i,1,5050) {
			int t = i, ok = 1;
			while (t) {
				if (t%10!=4 && t%10!=7) ok = 0;
				t /= 10;
			}
			k[i] = k[i-1] + ok;
		}
		
		int res = 0;
		rep(i,b-a-al+2) {
			int mn = 114514, l = a+i, r = l+al-1;
			rep(j,r-l-bl+2) {
				int ll = l+j, rr = ll+bl-1;
				chmin(mn, k[rr]-k[ll-1]);
			}
			chmax(res, mn);
		}
		return res;
	}
};