SRM669 div1 250
解答に必要なことを一つも考えつけてなかったorz
最適分割の部分の理解が怪しいが、理解したと思う範囲でまとめておく。
問題
体積Sのスライムがある。
1回の操作で、今あるスライムの塊を一つ選んで、2つに分解することができる。
このとき、体積Aのスライムを体積aと体積bに分解した場合、a*b点もらえる。(a,bは整数でなければいけない)
得点がM点になるために必要な操作の最低回数は何回か？
2<=S<=1000
1<=M<=10^9
考え方
「できるだけ大きい者同士を掛け合わせるほうが大きい得点が得られる」ことから、今あるスライムの中で一番大きい体積のものをできるだけ半分に分けていく、という方針が考えられるが、これは嘘解放。
例として、S=6の時、{6}->{4,2}->{2,2,2}と分解した場合、2回で12点が得られる。
これは、最初は得点が小さくても後で高得点が得られそうという可能性と、小さい数での総当たり実験で見つけられる。(そもそも上の方針だと証明できない)
S=6の場合で考えると、M=9なら{6}->{3,3}が選ばれるべきだし、M=12なら{6}->{4,2}->{2,2,2}が選ばれるべきで、「どのように分解するか？」をトップダウンに考えると、総得点Mによって選択が変わってしまう。全探索やDPとかで求めようとすると、状態数が多すぎて難しい。
そこで、二分探索+greedy的に考えてみる。
もし、K回分解すると仮定すると、M点以上得られるか調べて、一番小さいKを返せばよくなる。
(KはS-1回まで調べればよいので、二分探索でなくてもよい)
K回分解でM点以上得られるか？を考える。
K回分解するということが分かった場合に使える条件としては、「最終的に(K+1)要素に分解される」ことがある。
しかし、これでも、トップダウンに分解する方向で得られる得点を考えるのは難しいので、ボトムアップに考える。
ボトムアップ的に、結合する方向に得点を求めていってもトップダウンに計算する得点と同じになることがわかれば、次に進める。
以下、要素がa,b,c,dの4つに分解されたとして考える。
結合の仕方を変えて得点を計算してみると、
ab+cd+(a+b)(c+d) : {a,b,c,d}->{ab,c,d}->{ab,cd}->{abcd}
ab+(a+b)c+(a+b+c)d : {a,b,c,d}->{ab,c,d}->{abc,d}->{abcd}
cd+(c+d)b+(c+d+b)a : {a,b,c,d}->{a,b,cd}->{a,bcd}->{abcd}
= ab+ac+ad+bc+bd+cd ・・・①
と、結合の仕方によらず、同じ得点が得られることがわかる。
次に、このスコア①が得られる最大値を考える。
各要素は0より大きいので、、相加相乗平均の関係式から「(a+b)/2>=(a*b)^(1/2)」<=>「(a+b)^2/4>=a*b」であることを使って、
① <= (a+b)^2/4 + (a+c)^2/4 + (a+d)^2/4 + ・・・ + (c+d)^2/4
で、等号はa=b,a=c,a=d,b=c,b=d,c=d、すなわち、a=b=c=dの場合に成り立つ。
ただ、a,b,c,dは整数なので、できるだけ均等になるように用意すればよい。
したがって、「K回分解する場合に得られる得点」は、Sをできるだけ均等にK+1個に分解した場合の①の計算を行えば得られる。
また、①はそのまま計算しようとすると、O(K^2)だが、「1/2ΣAi*(S-Ai)」とも書け、O(K)で求められる。
