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$ の大小で解法を変えると楽なタイプの問題．
- 多倍長整数を使って二分探索するのは珍しい(必要ないはずだが)．
