roiti46's blog

主に競プロ問題の解説を載せてます

TopCoder SRM 655 Div2: Med

いらぬ条件を追加して本番は落としてしまった。

問題はこちらから

問題

WxHの折り紙を与えられる。この紙を折りたたんでいき、折り紙の面積をAにしたい。ただし折りたたむとき、折り目は縦か横の辺に平行でなければならず、折りたたんだ後でも各辺の長さは整数でなければならない。面積Aにするのに必要な折り畳み回数の最小値を答えよ。そのような折りたたみ方がないときは-1を出力せよ。

1 ≦ W, H ≦ 1,000,000,000、1 ≦ A ≦ 100,000

解法

Aの最大値が小さいことに注目する。仮に面積Aを実現できるとして、その一辺を全探索でシミュレートしていき、折り畳み回数を数えていく。その最小値が答えとなる。

一度の折り畳みで縦(横)を半分(辺の長さが奇数のときは少し異なる)まで折りたためるので、できるだけこの折りたたみをしていく。 Aを割り切れるw (1 ≦ w ≦ A)について、h = A/wとする。w ≦ W かつ h ≦ Hのとき、W < 2*wになるまでW = (W+1)/2としていく(Wを折りたたむ)。Hについても同様。 計算後、W > wならばWを折りたたんでwに、H > hならHを折りたたんでをhにしてしまう。

このときの折り畳み回数がA = w*hのときに必要な折り畳み回数の最小値となる。 あとはすべてのAを割り切るwについて、折り畳み回数の最小値をとれば答えとなる。 折り畳みが不可能かどうかはansが初期値のままかどうかで判断すればいい。

def solve(self, W, H, A):
    ans = 10**10
    for w in xrange(1,A+1):
        if A%w == 0:
            h = A/w
            if W >= w and H >= h:
                tmp = 0
                aw,ah = W,H
                while aw >= 2*w:
                    aw = (aw+1)/2
                    tmp += 1
                while ah >= 2*h:
                    ah = (ah+1)/2
                    tmp += 1
                if aw > w: tmp += 1
                if ah > h: tmp += 1
                ans = min(ans, tmp)
    return ans if ans < 10**10 else -1

まとめ

本番ではW ≧ Hにして、w ≧ A/w = h なwとhのみ探索するようにしていたがこれだと最小値を得ることのできないテストケースが存在した。その条件が本当に必要かどうかよく考えないといけない。

広告を非表示にする