kmjp's blog

競技プログラミング参加記です

TopCoder SRM 648 Div1 Medium KitayutaMart

本番自力だと時間切れっぽいな。
http://community.topcoder.com/stat?c=problem_statement&pm=13649

問題

K種類の商品があり、それぞれ1個目の価格は1~Kである。
価格iのものを複数買うこともできるが、買うたびに1個当たりの価格が倍になる。
すなわちj個目の価格は i*2^{j-1}となる。

N個の商品をそろえるとき、N個のうち最高価格を最小化せよ。

解法

自力でうまいアプローチが思いつかなかったので、writerヒントを参照した。
https://twitter.com/evima0/status/562247250869374977

 2^x~(2^{x+1}-1)の価格の商品は、min(K, 2^{x+1}-1)個買うことができる。
このことから、二分探索を用いてN個目の商品が 2^x~(2^{x+1}-1)に入るようなxを求めることができる。

まず 1~(2^x-1)の価格の商品の分は先にNから引いておく。
あとは 2^x~(2^{x+1}-1)の価格の範囲で、安い順にN個選択していけばよい。

では各価格の商品が何個ずつあるか。
例えばx==3の時を考えると、元々価格1~7の商品は何度か価格が倍になっているので、価格1~15の商品は以下のようになる。

元の価格 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
次の購入価格 8 8 12 8 10 12 14 8 9 10 11 12 13 14 15

上記表より、2^iの倍数の購入品は(i+1)個存在することがわかる。
ただし問題は、 K \lt 2^{x+1}-1の場合である。
例えばK==9なら価格11や13のものは買えないし、価格10のものも2個目が買えない。

各価格の購入数をうまく計算することが必要である。
これには、各価格の商品が何番目に出てくるか考える必要がある。
答えを書いてしまうと、価格vが 2^iの倍数の場合、初回登場してくるのは \frac{v}{2^i}個目で、以降2倍2倍の位置に登場する。
例えば購入価格12の商品は、元価格3,6,12のところで登場する。

この推測より、 \frac{v}{2^i}, \frac{v}{2^{i-1}}, \frac{v}{2^{i-2}}...とこの値がK以下である間そのような購入可能品があるので、その分Nからデクリメントしていけば良い。

なお、Kが小さい場合xが30を超え購入価格が10^9+7を超えることがあるので注意。
以下では一旦全体を 2^{x-\log K}程度割った値で計算し、最後にまた掛けている。

ll mo=1000000007;
ll modpow(ll a, ll n = mo-2) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

class KitayutaMart {
	public:
	ll NN,KK;
	ll sum(ll v) {
		ll tot=0;
		int i;
		FOR(i,v) {
			ll t=min(KK,(1LL<<(i+1))-1);
			tot+=t;
			if(tot>=1LL<<40) return tot;
			if(t==KK) return tot+(v-i-1)*KK;
		}
		return tot;
	}
	
	int lastPrice(int N, int K) {
		int i,x;
		NN=N,KK=K;
		if(N==1) return 1;
		ll L=0;
		for(i=29;i>=0;i--) if(sum(L+(1<<i))<N) L+=1<<i;
		N-=sum(L);
		
		x=0;
		while(1<<(x+1) <= K) x++;
		x=min(x,(int)L);
		if(L<29) K=min(K,(1<<(L+1))-1);
		for(int y=1<<x;;y++) {
			int r=y;
			while(r%2==0) r/=2;
			while(r<=K) {
				if(--N<=0) return modpow(2,L-x)*y%mo;
				r*=2;
			}
		}
	}
}

まとめ

自力では解けなかったものの、writeの簡略なヒントで解答までたどり着けたのは良かった。