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; } };