Codeforces Round #353 (Div. 2) C. Money Transfers

問題
Problem - C - Codeforces
行の銀行が円周上に並んでいる．隣の銀行に送金することが可能になっている．Aさんがそれぞれの銀行に口座を持っていて，お金を預けている（または借りている）．預けているお金を隣の銀行に送金することを繰り返し，すべての銀行の残高を０にしたい．送金する操作を最小にする問題．

解法
editorialの解法です．
最大の送金回数はになる．そこから何回減らすのかということが問題になる．減らせるということはある範囲で送金が完結していることを意味する．

1

-3

2

2

-2

ここでは[1:3],[4:5]でそれぞれ完結している．累積和をとるとこれを簡単に検出できる．

1

-2

0

2

0

0になっているところで送金が完結していることがわかる．この場合，最小の送金回数はになる．

-3

2

2

-2

1

のように1番目の銀行と番目の銀行を挟んで完結することもある．この時累積和は

-3

-1

1

-1

0

となっているため０を数えるだけではうまくいかない．しかし，右に１つずらすとすべてに１が足されて０が２つ出てくる．つまり，ずらしていき０の数が最大になった時が一番送金回数が少ない時になる．ここで，わざわざずらす必要はない．累積和をした時に最も多く出てきた数字が０になるようにうまくずらすことでこれを計算することができる．

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

#define RREP(i,s,e) for (i = s; i >= e; i--)
#define rrep(i,n) RREP(i,(int)(n)-1,0)
#define REP(i,s,e) for (i = s; i <= e; i++)
#define rep(i,n) REP(i,0,(int)(n)-1)
#define INF 100000000

typedef long long ll;

int main() {
    int i, n, ans;
    ll sum = 0;
    map<ll,int> mp;
    scanf("%d",&n);
    ans = n - 1;
    rep (i,n) {
        int a;
        scanf("%d",&a);
        sum += a;
        mp[sum]++;
        ans = min(ans,n-mp[sum]);
    }
    printf("%d\n",ans);
    return 0;
}