SRM648D1Med KitayutaMart

evimaさん回のMed.

問題概要(原文)

$K$ 種類のりんごがあり, $i$ 番のりんごは $i$ 円. $1$ 個買う毎に値段は倍になる. $N$ 個買った時にかかる金が最小のときに,最大の金額は? MOD $10^9+7$ で求めよ.

考察

安いやつから貪欲に買い続けるのが最適なのはすぐに分かる. $K$ が小さければ優先度付きキューを使って簡単にシミュレーションできる.

$K$ が小さくても,$N$ が大きいと,終わらなさそうに見えるが,いつかは $max(A) < min(A) \times 2$ となるようなタイミングが来る.ここからは周期に入るので繰り返し二乗法でショートカットできる.計算量は $O(Klog^2(K))$

$K$ が大きいとき,りんごの価格はそれほど大きくならない.最後に買った奴の値段を二分法で求める.値段をどんどん半分にしていく.計算量は $O(log^2(X))$ $X$ は解の最大値でおよそ $2^{250}$ 程度を見ておけば足りる.

ソースコード

using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class KitayutaMart
{
    public int lastPrice(int N, int K)
    {
        const long MOD = 1000000007;

        if (K <= 5000000)
        {
            N--;
            var pq = new BinaryHeapPriorityQueue();
            for (int i = 1; i <= K; i++) pq.Enqueue(i);
            while (N > 0)
            {
                var p = pq.Dequeue();
                if (p * 2 >= K)
                {
                    pq.Enqueue(p); break;
                }
                pq.Enqueue(p * 2);
                N--;
            }
            if (N == 0) return (int)(pq.Dequeue() % MOD);
            var k = N / K;
            N %= K;
            var a = pq.heap.ToArray();
            Array.Sort(a);
            var ans = ModPow(2, k, MOD) * a[N];
            return (int)(ans % MOD);

        }
        else
        {
            BigInteger l = 0, r = BigInteger.Pow(2, 250);
            for (int _ = 0; _ < 255 ; _++)
            {
                var m = (l + r) / 2;
                BigInteger cnt = 0;
                BigInteger v = m;
                while (v > 0 && cnt < N)
                {
                    cnt += BigInteger.Min(v, K);
                    v /= 2;
                }
                if (cnt >= N)
                    r = m;
                else l = m;
            }
            return (int)(r % MOD);
        }
    }
    static public long ModPow(long x, long n, long mod)
    {
        long r = 1;
        while (n > 0)
        {
            if ((n & 1) == 1)
                r = r * x % mod;
            x = x * x % mod;
            n >>= 1;
        }
        return r;
    }
}
#region PriorityQueue by BinaryHeap
public class BinaryHeapPriorityQueue
{
    public readonly List<long> heap;
    private int size;
    public BinaryHeapPriorityQueue()
    {

        this.heap = new List<long>(5000000);
    }
    public void Enqueue(long item)
    {

        this.heap.Add(item);
        var i = size++;
        while (i > 0)
        {
            var p = (i - 1) >> 1;
            if (this.heap[p] <= item)
                break;
            this.heap[i] = heap[p];
            i = p;
        }
        this.heap[i] = item;

    }
    public long Dequeue()
    {
        var ret = this.heap[0];
        var x = this.heap[--size];
        var i = 0;
        while ((i << 1) + 1 < size)
        {
            var a = (i << 1) + 1;
            var b = (i << 1) + 2;
            if (b < size && heap[b] < heap[a]) a = b;
            if (heap[a] >= x)
                break;
            heap[i] = heap[a];
            i = a;
        }
        heap[i] = x;
        heap.RemoveAt(size);
        return ret;

    }
    public int Count { get { return size; } }
    public bool Any() { return size > 0; }
}
#endregion

コメント

  • $K$ の大小で解法を変えると楽なタイプの問題.
  • 多倍長整数を使って二分探索するのは珍しい(必要ないはずだが).