SRM648div1med:KitayutaMart

問題:http://community.topcoder.com/stat?c=problem_statement&pm=13649&rd=16312

解法:まず基本として、値段が小さいものから順に買っていくのが最適である。ということで、値段の小さい順に選んでいった時、N番目のものは何かを求めれば良い。
KやNはかなりでかいので、普通に数えていっても間に合わない。そこで、まずアバウトに小さい方から数えていくことを考える。具体的には、以下のようなことを考える。

①区間[1,K]という範囲から、適当な操作をして区間[K+1, 2*K]に値段を変える
②区間[K+1,2*K]という区間に変えると、あとは区間[2*K+1,4*K],[4*K+1,8*K],...というように区間を変えていくのは容易(それぞれの数を1回ずつ2倍すれば良い)。それぞれの区間から次の区間に変えるために掛け算する回数はK回

以上のことを考えながら解法を作る。
まず①にするのにかかる回数を考える。区間[K+1,2*K]にするには、
①まず1〜Kを2倍する
②(元の数が)1〜K/2を2倍する
③(元の数が)1〜K/4を2倍する...
と操作をしていけば良いのでかかる回数は,K+K/2+K/4+...となる。
Nがこの回数(numとする)以下の時は、解は区間[1,2*K]にあることになる。ここで、f(x)を、「値段がx以下になるような商品の総数」とすれば、求める数は、f(x) >= Nかつf(x-1) < Nを満たす数になる。このf(x)は①にかかる回数を求めるのと同様に計算できて、f(x)=min(x,K)+min(x,K/2)+...となる。よって、求めるxの値を2分探索すれば良い。

Nがnumより大きい時は、上の②の事実を使う。M=N-numとすると、2を掛け算する回数はp=(M-1)/K回。また、区間[K+1,2*K]のうちで小さいものから数えてM-p*K番目のものを求めなければならないが、これは上と同様に二分探索で計算することができる。

以下ソースコード

ll getNum(int K) {
    ll ret = 0;
    while (K) {
        ret += K;
        K /= 2;
    }
    return ret;
}

ll get(ll x, ll K) {
    ll ret = 0;
    while (x) {
        ret += min(K, x);
        x /= 2;
    }
    return ret;
}

const ll MOD = 1e9+7;

// x^p
ll pow_mod(ll x, ll p, ll m = MOD) {
    if (x == 0) return 0;
    if (p == 0) return 1;
    if (p == 1) return x;
    if (p % 2 == 0) {
        ll tmp = pow_mod(x, p/2, m);
        return (tmp * tmp) % m;
    } else {
        return (x*pow_mod(x, p-1, m)) % m;
    }
}

class KitayutaMart {
public:
    int lastPrice(int N, int K) {
        ll num = getNum(K);
        cout << num << endl;
        if (num >= (ll)N) {
            ll low = 0, high = 2*K;
            while (high - low > 1) {
                ll med = (high + low) / 2;
                if (get(med, K) >= N) high = med;
                else low = med;
            }
            return (int)high;
        }
        // N is big
        int M = N-num;
        ll p = (M-1) / K; // 2をかける回数
        ll q = M - p*K;
        ll low = K, high = 2*K;
        while (high - low > 1) {
            ll med = (high + low) / 2;
            if (get(med, K)-get(K, K) >= q) high = med;
            else low = med;
        }
        printf("high is %lld, p is %lld\n", high, p);
        return (pow_mod(2,p)*high) % MOD;
    }
};