本番自力だと時間切れっぽいな。
http://community.topcoder.com/stat?c=problem_statement&pm=13649
問題
K種類の商品があり、それぞれ1個目の価格は1~Kである。
価格iのものを複数買うこともできるが、買うたびに1個当たりの価格が倍になる。
すなわちj個目の価格はとなる。
N個の商品をそろえるとき、N個のうち最高価格を最小化せよ。
解法
自力でうまいアプローチが思いつかなかったので、writerヒントを参照した。
https://twitter.com/evima0/status/562247250869374977
の価格の商品は、min(K,)個買うことができる。
このことから、二分探索を用いてN個目の商品がに入るようなxを求めることができる。
まずの価格の商品の分は先にNから引いておく。
あとはの価格の範囲で、安い順に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==9なら価格11や13のものは買えないし、価格10のものも2個目が買えない。
各価格の購入数をうまく計算することが必要である。
これには、各価格の商品が何番目に出てくるか考える必要がある。
答えを書いてしまうと、価格vがの倍数の場合、初回登場してくるのは個目で、以降2倍2倍の位置に登場する。
例えば購入価格12の商品は、元価格3,6,12のところで登場する。
この推測より、とこの値がK以下である間そのような購入可能品があるので、その分Nからデクリメントしていけば良い。
なお、Kが小さい場合xが30を超え購入価格が10^9+7を超えることがあるので注意。
以下では一旦全体を程度割った値で計算し、最後にまた掛けている。
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の簡略なヒントで解答までたどり着けたのは良かった。