kojingharangの日記

SRM 648 Div1 550 KitayutaMart

13:29 |

• i*2^j (1≦i≦K, 0≦j) 円のりんごが 1 個ずつある。合計金額が最小になるように N 個買った時、最高値のりんごの値段を mod 10^9+7 で求めよ。
• N, K≦10^9

• ぬぬぬ
• 表を 1 コずらして 2 で割ると元の表と同じになるから、そんな感じで再帰でわーっとやるのかな
• 合計が最小になるように買うということは i*2^? を買うなら I*2^? (I≦i) はすべて買うはずだ
• f(N) = (合計, 最高値) として
• f(N) = どこまでの i を買うかを K 種類ためしつつ、Sum, V = f(N-今取ったやつ) として (Σi+Sumが最小になるやつ, その時のV)
• でなんか規則的だから調べる i は実はすごく狭いのかな...
• わからん

• あとで

• 最高値が V のときに買った総数 n_upto(V) は規則的ゆえに分かるので、V で二分探索すればいいのか
• (N,K)=(1000000000,1) のとき V が大きすぎてだめだ...

• Lepton さんの記事をみる
• http://lepton.hatenablog.jp/entry/2015/02/02/234238

• 最高値が K+1 以上のときは K のりんごは必ず L 個買うとする
• i*2^j (1≦i≦K, 0≦j≦L) の KL 個も必ず買うことになる
• L は、1 ≦ N-KL ≦ 最高値が K のときに買う個数 な最小の L がいいっぽい
• 例えば (N,K)=(41,10)だと n_upto(10)=18なので (L,残り)=(3,11),(4,1)がありうる
• 答えは n_upto(X)≧残り な最小の X について max(K*2^L, X*2^L (ずれた分) )ということで
• L=3 なら X=7, 答え=56
• L=4 なら X=1, 答え=80
• ...みたいに, うまく証明できないけど L は小さい方が良さそう
• (詳しくは http://dojiboy9.atspace.cc/contest/view-post.php?p=kitayutamart に書かれているのかもしれない)

• ということでそんな感じで書いた
• Accepted in practice
• もやもやが残る...

// num of cells which value <= v
ll n_upto(ll v) {
	ll ans = 0;
	while(v) {
		ans += v;
		v/=2;
	}
	return ans;
}

ll lb(int N, int K) {
	ll lo=0, hi=K;
	// n_upto(lo)<N<=n_upto(hi)
	while(lo+1<hi) {
		ll mid = (lo+hi)/2;
		if(N<=n_upto(mid)) hi=mid; else lo=mid;
	}
	return hi;
}

class KitayutaMart {
	public:
	int lastPrice(int N, int K) {
		ll countWithinK = n_upto(K);
		ll fillCount = N - countWithinK;
		ll fillLines = (fillCount + K - 1) / K;
		ll restCount = N - fillLines*K;
		return (modll(2)^fillLines) * lb(restCount, K);
	}
};

ツイートする