WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM683 Div1 Easy "MoveStones"

Editorial

https://apps.topcoder.com/wiki/display/tc/SRM+683

まずは簡単に考えて、石の山が円状に並んでいないものとしよう。ちょうど、類題であるDiv2 Mediumでは石の山は直線状になっており、最後と最初の山が隣り合っていなかった。これの解法はO(n)の時間を要した。

円状の場合の解法は、石が山の間をn回以上移動する必要はなく、そのような動きは冗長である。なので、すべての隣り合う山において石を交換する必要はない。2つの山を左端・右端として(隣り合っていないとみなして)Div2バージョンのように解くことができる。よって、全てのO(n)の候補を試し、その最小値を返せばよい。

事後

「石が山の間をn回以上移動する必要はない」ってのがよく分からん!

ソースコード

class MoveStones {
    public:
    long long get(vector<int> a, vector<int> b) {
        int n = a.size();

        // おかしいやつ検出
        long long sa = 0, sb = 0;
        for (int i = 0; i < n; i++) {
            sa += a[i], sb += b[i];
        }
        if (sa != sb) return -1;

        // こっからおかしくないやつ
        long long ans = 1e18;
        // start地点を決めて回す(直線状と考える)
        for (int start = 0; start < n; start++) {
            long long cnt = 0;
            long long over = a[start] - b[start];
            for (int i = 0, cur = next(start, n); i < n - 1; i++, cur = next(cur, n)) {
                cnt += abs(over);
                over += a[cur] - b[cur];
            }
            // 最小をとっていく
            ans = min(ans, cnt);
        }

        return ans;
    }

    // 次のindexを返す
    int next(int i, int n) {
        return i + 1 == n ? 0 : i + 1;
    }
};