SRM683 Div.1 Easy MoveStones

前回のするめでめでたくDiv.1に上がれたので、今日からDiv.1Easyの問題を解いています。

次回何とか1完できることを目指して。

問題

https://community.topcoder.com/stat?c=problem_statement&pm=14174

石が縦に積まれたn個の山が、円状に隣り合って並んでいる。石の初期配置aを、所望の配置bにする最小回数を求めよ。ただし許される操作は、石の山の一番上にある石を隣り合う山の一番上に動かすことだけである(石が0個の場合も山とみなすので、飛ばしてはいけない)。所望の配置を得られない場合には-1を出力せよ。

制約

解法

貪欲法で解く。まず、円環の問題の王道として、「任意の位置で区切って線分として考える」という手法がある。この問題も、すべての山の間(n箇所)について区切って、動かし方の最小値を求めればよい。*1

直線に変形した各区間については、Div.2Medと同様に解ける。まずaとbの差分dをとる。dを左から走査し、各iに対し、もしd[i] > 0なら右にd[i]個の石を動かせばよい。d[i] < 0なら右側の最も近い空でない山から石をもらうことになるが、これはiからマイナス個の石を右に動かすと考えるとd[i] > 0のときと同様に扱える。つまりd[i+1] += d[i]とsm += abs(d[i])を繰り返していけば答えがsmとして得られる。

コーナーケースとして、sum(a) != sum(b)のときは所望の配置が得られないことに注意。

以下のコードでは円を表現するために同じ配列を2つつなげている。

class MoveStones:
    def get(self, a, b):
        if sum(a) != sum(b):
            return -1

        N = len(a)
        d = [0] * N
        for i in range(N):
            d[i] = a[i] - b[i]
        d += d

        mi = float("inf")
        # where to separate
        for i in range(N):
            t_d = d[i:i+N]
            sm = 0
            # distance from i
            for j in range(N-1):
                t_d[j+1] += t_d[j]
                sm += abs(t_d[j])

            if t_d[-1] == 0:
                mi = min(mi, sm)

        return mi

所要時間: 10分程度

Div2medと同じだったのでこれはさくっと解けた。

*1:円を切っていい理由は以下のように説明できる。区切った区間を0..n-1とすると、もしn-1から0へ石が移動するなら山0からは出る石aと入る石bが存在することになる。この操作は山の高さを変えないので無駄である。よって線分内の移動のみ考えればよい。