SRM 510 DIV1 Medium TheLuckyGameDivOne

SRM 単純な戦略 数値の桁ごと

http://apps.topcoder.com/stat?c=problem_statement&pm=11463&rd=14439

問題

10進法表現に4と7のみしか現れない数をlucky numberと呼ぶ。
今、positive上に[a,b] (1<=a<=b<=10^10)の区間がある。
初めに、Johnは[a,b]に含まれ、長さがjLen(1<=jLen<=b-a+1)である連続した区間[ja,jb]を選ぶ。
次に、Brusは[ja,jb]に含まれ、長さがbLen(1<=bLen<=b-a+1)である連続した区間[ba,bb]を選ぶ。
最後に、[ba,bb]に含まれるlucky numberの数を数える。
Johnはできる限りその数が大きくなるように選び、
Brusはできる限りその数が小さくなるように選ぶとき、その数を答えろ

回答

[a,b]に含まれるlucky numberの数はたかだか sum (map (2^) [1..10]) == 2046 であって、つまりその二乗*α程度なら問題ない。
ここで、戦略を考える。
Brusはできるだけ少なくするのに、lucky number[i] == ba+1 となるところを選ぶ戦略ができる。(たぶん)
ただし、それが何も選べない場合もあって、そういう場合はどこでも同じだと思う。
Johnはできるだけ多くするのに、 ja == lucky number[i] - bLen + 1 となる所を選ぶ戦略ができる。たぶん。できるだけ含めないといけないlucky numberを多くする、的な。
さて、この戦略を全てのlucky numberに対して試し、それぞれの数がわかればいい。
数を数える方法は下記参照

コメント

初めて？かもしれないけど、DIV1 Mediumが自力で解けた。ただし、時間はかかりまくって167.06ptだけど。
結構、何番目か、を得るのに苦労した。だが、upper_boundが使えると思いついて、とてもいいと思った。

vector<T> v;
//vに対象となるものを全てpush_backしてソートしておく
int count(T x) {
    return upper_bound(all(v), x) - v.begin();
    //対象となるもの以下にいくつの要素(要素の個数)があるかを返す
}
count(r) - count(l-1) //区間[l,r]の場合
count(r-1) - count(l-1) //区間[l,r)の場合

コード

#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define aut(v, x) __typeof(x) v = (x)
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;
typedef long long ll; typedef vector<int> vi; typedef pair<int,int> pii; typedef vector<pii> vpii;
const int INF = 0x3f3f3f3f; const ll INFL = 0x3f3f3f3f3f3f3f3fLL;

struct TheLuckyGameDivOne {
	vector<ll> v;
	int count(ll x) {
		return upper_bound(all(v), x) - v.begin();
	}
	int find(long long a, long long b, long long jLen, long long bLen) {
		int r = 0;
		rer(i, 1, 10) rep(j, 1<<i) {
			ll x = 0;
			rep(k, i) x = x * 10 + (!((j>>k)&1) ? 4 : 7);
			v.pb(x);
		}
		sort(all(v));
		rep(i, 100) cout << i << ": " << count(i) << endl;
		each(x, v) {
			if(!(a <= *x && *x <= b)) continue;
			ll t = *x - bLen + 1;
			if(t < a) t = a;
			ll u = t + jLen - 1;
			if(u > b) continue;
			int l = INF;
			l = min(l, count(t+bLen-1) - count(t-1));
			each(x2, v) {
				if(!(t <= *x2 && *x2 <= u)) continue;
				ll t2 = *x2 + 1;
				ll u2 = t2 + bLen - 1;
				if(u2 > u) continue;
				l = min(l, count(u2) - count(t2-1));
			}
			if(l != INF) r = max(r, l);
		}
		return r;
	}
};