SRM 683 div1 easy: MoveStones

問題

TopCoder Statistics - Problem Statement

解法

円環の問題では, 円環のまま考えるのではなくどこかでぶった切って直線にして考えるのが定石です。今回の問題でもその手法が使えます。

移動する石の数は, 隣接している皿同士を結ぶ辺について, 「その辺を移動する石の数」の和として考えることが出来ます。

a0 から a1 に放出する石の数が決定すれば他の辺上を移動する石の数も決定するので全体で移動する石の数が決まりますが, この時すべての辺から石が移動するのは得をしないのでないと考えてよいです(石の移動が 5 -> 4 -> 7 のように全部正負が一致しているなら明らかに無駄なのでひとつの辺を 0 にするべき。また, どこかで正負が入れ替わっているとすると, どこかの皿からは隣接する２つの皿に石を分配し, どこかの皿は隣接する２つの皿から石を受け取る。この時, 石は両方向から受け取らないで片方から受け取るように出来る)。よって, 解法としては石の移動に使わない辺を全探索して, 各場合にシミュレーションして最小回数を求める, というようになります。

class MoveStones {
public:
    long long get(vector <int> a, vector <int> b) {
        int n = a.size();
        ll sum = 0;
        for (int i = 0; i < n; i++) sum += a[i]-b[i];
        if (sum) return -1;
        ll ans = 1ll<<60;
        for (int i = 0; i < n; i++) {
            ll tmp = 0, now = 0;
            for (int j = 0; j < n; j++) {
                now += a[j];
                tmp += abs(b[j]-now);
                now -= b[j];
            }
            ans = min(ans, tmp);
            vi na(n), nb(n);
            for (int j = 0; j < n; j++) {
                na[j] = a[(j+1)%n];
                nb[j] = b[(j+1)%n];
            }
            a = na, b = nb;
        }
        return ans;
    }
};