TopCoder SRM461 Div1Hard

Div1Hard2問目。

問題

フェンスがいくつかある。これらを使って、できるだけ広い面積を囲いたい。囲いは長方形の形で、、一辺が長い壁で、あとの三辺はフェンスで作る。もろいノコギリがあって、フェンスを１回だけ切断できる。できるだけ広い面積を囲うとき、壁に平行な部分の長さを求めよ。

解法

当然だが、使わないフェンスは出ない。余ったら、壁に平行な方向に取り付ければいい。
フェンスの切断の意味を考える。切断したら２つの短いフェンスができる（便宜上、切断しない場合は片方が長さ0になるように切断すると仮想する）。この切断したフェンスの使いどころは、「壁に平行な辺＋壁に垂直な辺」か、「壁に垂直な辺２つ」である。ここで、壁に垂直な辺の長さを１つ決定すれば、うまく切断することで反対側の辺も作れる。
壁に垂直な辺の長さはどれくらいだと嬉しいか考える。この長さをx、フェンスの長さ合計をlとすると、面積S=x(l-2x)=-2x^2+l*xである。ここで、S'=0⇔x=l/4であるから、壁に垂直な辺の長さはl/4とするのが理想である。すなわち、できるだけxをl/4に近づけるようにすればよい。
この「近づける」という操作は、普通にナップザック問題を準多項式時間で解いたり、全探査を行ったりすると時間やメモリが足りなくなる。フェンスの数が40以下であることを利用して、半分ずつに分けて可能な長さを求め、ソートする。これを組み合わせるようにして求めればよい。
前の議論で、「壁に垂直な辺」の長さか「壁に平行な辺」の長さを決定すれば面積も決定することがわかった。前者の場合はl/4に、後者の場合はl/2に近づければよい。これにより、答えがO(N*(√2)^N)程度で求まる。