冬休みももう終わりですね。
ここを放置気味でしたが、こういう場所を作ったからにはちゃんと何か書いていこうと思ったので。
表題の問題を解きました。3日くらいかけてやっと解きました。
＜問題概要＞
n個の微生物がいる。それぞれが変な物質を出している。
各個体の物質の放出量と許容量が与えられる。
複数の微生物を同じ箱に閉じ込めたとき、1体の微生物が摂取する物質は全体の放出量の平均値
最も条件良く微生物たちを選んだとき、最大何匹を同じ箱に入れられるか？
＜解法＞
・とりあえず平均値を固定して、許容量がそれ以上の物の中で小さい物からGreedyすることを考えた
・座圧を使って各個体毎の許容量の値のみで考えるとO(N^2)程度-＞部分点30点を得られる。
・上の考えにおいて、ある平均値についてO(N)で判定を行うのは少し計算量的にキツいかも･･･
・各個体の放出量の合計値が、(考えている許容量×個体数)より大きくなるようにしたから定めていく-＞累積和が使えそう
・累積和をO(log N)くらいで計算するには-＞BIT(Binary Indexed Tree)
・ただし、小さい方から取りたいので昇順ソート
・問題文のサンプルデータでやるとこういう木になる([7],[8]は不要)
・許容量を段階的に考えていくとき、許容量がそれ以下の微生物の値については0に変えていく
・あとはここで二分探索をする
・50点を取る方法
O(N log^2 N)で50点が返ってくる。この問題の部分点としては設定されていないが、個人的にはこれを小課題2にしてもいいのでは？と思った。
・例えば、許容量4の時を考える(赤字はその区間に含まれる個数)
N(この場合は6)までで二分探索すると、
・3->1～3の累積和:13、1～3の個数:3->4*3=合計12まで放出してok->NG
・1->1～1の累積和:2、1～1の個数:1->4*1=4まで放出してok->OK
・2->1～2の累積和:7、1～2の個数:2->4*2=8まで放出してok->OK
という風な感じで、2体までならokになる。
許容量7の時も考えてみる。
今度は、一番左の微生物の許容量が4のため、これを虚無に置き換える。
個数に注意しながら探索すると
・3->1～3の累積和:11、1～3の個数:2->7*2=合計14まで放出してok->OK
・4->1～4の累積和:21、1～4の個数:3->7*3=21まで放出してok->OK
・5->1～5の累積和:33、1～5の個数:4->7*4=28まで放出してok->NG
という風にして4に定まりますが、1～4に実際にいる微生物はこの段階では3体なので、3を更新値にします。
・毎回BITのsumクエリを呼び出していると、許容量を試すのにO(N)、二分探索にO(log N)、BITのクエリの呼び出しにO(log N)かかるため、合計でO(N log^2 N)になります。
・BITは木構造の一種なので、実はO(log^2 N)をO(log N)にまとめることができます。
・BIT上二分探索という手法。
再登場。
今まで意味を持たなかった[8]がここで意味を持つようになります。
・まず全体をカバーしている[8]を見る。5体いるので7*5=合計35まで放出可能だが、35<46より答えは左側
・つぎに[4]を見る。3体いるので7*3＝21。放出量も21なので右側に行ける。
・[6]のノードへ移る。現在、これより左では放出21・許容21より、限界まで受け止めていることになる。よって、余裕は0。
2体なので7*2=14、これより左の余力が0なので受容可能なのは14だが、25出してくるのでできない
という風に、見ているノードの幅がだんだん1/2になっているのがわかると思います。
二分探索は「次に左と右のどちらのノードに行くか」といったところでしょうか。
この解法は、一つの区間に対する和の取得がO(1)でできるので、全体でO(N log N)です。
自分の提出を貼っておきます。
