読者です 読者をやめる 読者になる 読者になる

h_nosonの日記

競プロなど

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

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

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

1 -3 2 2 -2

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

1 -2 0 2 0

0になっているところで送金が完結していることがわかる.この場合,最小の送金回数は5-2=3になる.

-3 2 2 -2 1

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

-3 -1 1 -1 0

となっているため0を数えるだけではうまくいかない.しかし,右に1つずらすとすべてに1が足されて0が2つ出てくる.つまり,ずらしていき0の数が最大になった時が一番送金回数が少ない時になる.ここで,わざわざずらす必要はない.累積和をした時に最も多く出てきた数字が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;
}