SRM648: 550 - KitayutaMart

問題文

解法

現地点で一番安い(複数ある場合はどれでも良い)りんごを買い続ける方法が一番合計金額を安くできる.j このような買い方をしたときに,\(i\)回目の買い物の値段を\(p(i)\)として, $$ f(x) := 「p(i) \le x をみたす i の最大値」$$ とすると,\(1 \le x \le K\) の範囲では, \( f(x) := x + x/2 + x/4 + … \) となる. これは,値段\(2^a \times b\)になる品物の個数が\(a + 1\)個ということからわかる.

一番高いりんごの値段を\(t\)とすると,\(f(t-1) < N \leq f(t)\)をみたす.

\( f(i) \) が直接計算できるときは, 上式を満たす\(t\)を二分探索することで計算できる. \( f(K) \geq N \) のときは直接計算できるので二分探索すればよい.

\( f(K) < N \)のときは,直接二分探索はできないのでもう少し考える必要がある. ここで,品物の買い方を考えてみる. 余った購入回数を \( M := N - f(K) \) とすると, \(M\)回のうち\(P := floor((M-1) / K)\)回がそれぞれの品物に割り振られるということが,値段の増え方から分かる.

\( f(K) \)回買い終わった後の値段は\([K+1, 2K]\)に収まる. その中で \( L := M - P * K \) 番目の値段を \(y\)とすると, 一番高いりんごの値段は\(y \times 2^P\)となる. \( K+1 \le x \le 2K\)の範囲では\( f(x) = K + x/2 + x/4 + … \)で計算できるので, \(y \)は同様に二分探索で計算できる.

ソースコード

コンテスト中に書いたソースコード.

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)
 
using namespace std;
typedef long long LL;
 
 
const LL MOD = 1000000007;
 
class KitayutaMart {
public:
    LL N, K;
    LL f(int x) {
        LL ans = 0;
        while(x > 0) {
            ans += x;
            x /= 2;
        }
        return ans;
    }
    LL power(LL n, LL b) {
        LL res = 1;
        LL p = n % MOD;
        while(b > 0) {
            if(b & 1) res = (res * p) % MOD;
            p = (p * p) % MOD;
            b /= 2;
        }
        return res;
    }
    int lastPrice(int N_, int K_) {
        N = N_;
        K = K_;
        LL first = f(K);
        if(N <= first) {
            // x + 1 \in [1, K]
            // x     \in [0, K)
            int lb = 0, ub = K;
            while(ub - lb > 1) {
                int x = (lb + ub) / 2;
                if(f(x) < N) {
                    // [x, ub)
                    lb = x;
                } else {
                    // [lb, x)
                    ub = x;
                }
            }
            return lb + 1;
        } else {
            LL rest = N - first;
            // rest > 0
            rest --; // (0 based)
            // [K+1, 2K]
            LL pow = rest / K;
            LL NN = rest % K + 1; // (1based)
 
            // x + 1 \in [K+1, 2K]
            // x     \in [K, 2K)
            int lb = K, ub = 2*K;
            while(ub - lb > 1) {
                int x = (lb + ub) / 2;
                int eval = f(x) - first - (x - K);
                if(eval  < NN) {
                    // [x, ub)
                    lb = x;
                } else {
                    // [lb, x)
                    ub = x;
                }
            }
            LL ans = lb + 1;
            ans = (ans * power(2, pow)) % MOD;
            return ans;
        }
    }
};