スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Codeforces Round #165 (Div. 1) A : Magical Boxes

n 種類の箱がある。
i 種類目の箱は a_i 個あり、その大きさは k_i である。

小さい箱は大きい箱に入れることができる。
大きさ k の箱には大きさ k-1 の箱が高々 4 個入る。
大きさ k の箱には大きさ k-2 の箱が高々 4^2 個入る。などなど。

すべての箱が入るような箱を一つ作りたい。この箱は最小でどれだけの大きさにすればよいか。

・ 1 ≦ n ≦ 10^5
・ 0 ≦ k_i ≦ 10^9
・ 1 ≦ a_i ≦ 10^9

解答

明らかに異なる大きさの箱どうしは干渉しないので、各 k_i に対して a_i 個の箱が入る最小サイズの箱を求めれば、それらの max が答えになる。

大きさ k の箱が
・ 1 個あるとき、大きさ k+1 の箱に全部入る
・ 2 個あるとき、大きさ k+1 の箱に全部入る
・ 3 個あるとき、大きさ k+1 の箱に全部入る
・ 4 個あるとき、大きさ k+1 の箱に全部入る
・ 5 個あるとき、大きさ k+2 の箱に全部入る
・ 6 個あるとき、大きさ k+2 の箱に全部入る
……
・ 16 個あるとき、大きさ k+2 の箱に全部入る
・ 17 個あるとき、大きさ k+3 の箱に全部入る
……
という感じになるので、大きさ k + log_4(a_i) くらいの箱を用意すればよい。

a_i = 1 のときだけ例外なので十分注意する。( evil corner case!!! )

計算量は O(n log a)。ただし a = max_i a_i。

ソースコード

http://www.codeforces.com/contest/269/submission/3048724

スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。