TopCoder Single Round Match 774

　Easyは解けたつもりだったのですが、システムテストで落ちて0完でした。

Div1 Easy LandSplitter

 kmjpさんのブログに解説があります。

　まず、元の問題文には三個の分割と二個の分割が乗っているが、結局コストは同じなので、二個の分割だけ使うと考えて良い。また、コストは分割の順番によらない。

　その上で、できるだけ大きな要素を作るのが最善。これは、A<B<C<Dのとき、A*D<B*Cなので、(B, C)という分割より(A, D)という分割の方が良いことから考えていけば分かる。

　ここまではコンテスト中に分かっていて、Bを使う回数を大きい順に試していく実装を考えていました。

　まず、

・残りxのとき, A～Bを使って分割可能か

　は簡単に計算できる。これは、Aを使える回数をt=x//A回としたとき、t*A+(Bを使うときの誤差分である（B-A）*t)　以下にxがあれば良い。

　なので、Bを大きい順に試し、分割可能だったら、それがBを使う回数。（A=Bのときを例外処理しておけば、計算量は抑えられる。Bを使う回数は最大N/B回だが、Bを最大に使ったときの余りが高々B-1で、Bを使う回数を減らすごとに最低でも1ずつ縮まるので、高々min(B/(B-A), N/B)回にはなる。なので、$O(\sqrt{N})$か。）
　
　で、コンテスト中はその後の実装がまずく（次に何を使えばいいかをB-1から大きい順に試していた）TLEになってしまっていた。

　できるだけ大きい要素を作るように分割しているので、残りの分割が「Aが何個かとA以上B未満のものが1個」になると言える。それを考えると、NからBを使った残りをM、残りのAを使う回数useaとすると、

・M-A*usea<B

　を満たす最大のものがuseaとなり、O(1)で求めることができる。

　TopCoderは他人のコードが見られなそうなので、一応コードを載せておきます。これでシステムテストは通りました。
　なお、TopCoderはPython2なのでrangeじゃなくxrangeにしています（rangeだとMLEした）。

class LandSplitter():
    def cheapest(self, N, A, B):
        if A==B:
            if N%A!=0:
                return -1
            else:
                x=N//A

                return A*A* (1+(x-1))*(x-1)//2

        def check(x,A,B): # 残りxのとき, A～Bを使って分割可能か調べる
            t=x//A
            s=B-A
            if x<=t*(A+s):
                return 1
            else:
                return 0

        for useb in xrange(N//B,-1,-1): #Bを使う回数を大きい方から探索して,
            if check(N-useb*B,A,B)==1: #分割可能なときにBを使う回数とする.
                break
        else:
            return -1 # 分割可能なことがなければ、不可能

        
        M=N-useb*B # Bを使った残り
        ANS=M*(useb*B)+B*B*((1+(useb-1))*(useb-1)//2) # ここまでのコスト

        usea=max(0,-(-(M-B)//A)) # Aの使用回数
        
        if usea==0: # Aを使わなくて良いときは既に分割できている
            return ANS
        
        S=M-usea*A # Aを使った残り
        ANS+=S*(usea*A)+A*A*((1+(usea-1))*(usea-1)//2) # 残りのコスト
        return ANS