SRM421 Div1 normalがわからない

TopCoder

http://www.topcoder.com/stat?c=problem_statement&pm=10074&rd=13512
整数のリストが与えられる。これはケーキのサイズ。これを最大maxCuts回切って、一番大きい断片と一番小さい断片のサイズの差が一番小さくなるようにせよ、という問題。どうするんだこれ。

CONSTRAINTS

  • weights will contain between 1 and 50 elements, inclusive.
  • Each element of weights will be between 1 and 1,000,000,000, inclusive.
  • maxCuts will be between 1 and 100,000, inclusive.

切断数を1個ずつ増やしながら探索するとかでは無理そう。ケーキのサイズは最大1,000,000,000で、許される切断の回数は最大100,000回。ケーキは最大50個。

ちなみに問題文には書かれていないけども、ケーキをn回切るときにはn等分すると考えていい。なぜかというと、等分してない場合で、断片のどれかが最大もしくは最小になる場合、等分すれば最大の断片はもっと小さくなり、最小の断片はもっと大きくなるので、より「差の小さい」状態が存在することになる。逆に最大でも最小でもない場合、答えに影響しないので等分でもかまわない。よって常に等分する条件を付け加えても答えは変わらない。

        • -

漠然と考えてわからないときは端から考える。まずケーキが1個のときは分割数関係なく0.0を返す。ケーキがいくつかあって分割数の上限が0回の場合、答えはたんに最大値と最小値の差。

ケーキが2個あって、分割数が1の時を考える。分割するのは大きい方。大きい方をa, 小さい方をbとする。a == bなら分割しなくていい。分割後の差b - a / 2がa - bより大きければ分割しないでいい。つまりbがa * 3 / 4より大きければ分割する必要がある。

分割数は1のままで、ケーキがたくさんある場合。分割するのは最大のケーキ。なぜなら、そうでない場合は最大と最小の差が変化しないか増えるかのどちらかだから。最大のピースを分割して、最小を下回らない場合、これは他のピースのサイズによらず差が縮まる。下回る場合が厄介。つまりmax / 2 < min の場合、2番目に大きいケーキを2ndとして、max - min > 2nd - max / 2 が成り立つかどうかが分かれ目。

うーん。

切断数の上限が2の場合、maxを3分割する選択肢と、maxと2ndをそれぞれ2分割する選択肢がある。

うーん、道筋が見えないぞ。

(続きは後で書く)