Vasya and Arrays [Educational Codeforces Round 50 (Rated for Div. 2) D]

http://codeforces.com/contest/1036/problem/D

N要素の配列A, M要素の配列Bがある。
2つの配列に対して、「配列内の任意の区間を消して、その場所にその区間の総和を入れる」操作をする。
以上の操作を好きなだけやって、配列Aと配列Bを全く同じものにする。
同じものにしたときの配列の要素数の最大値を求めよ。
同じものにできない場合は-1を答えとする。

前提知識

• 尺取法

解法

http://codeforces.com/contest/1036/submission/42624389

まず、同じものにできない場合を考える。
どちらの総和を取って、それが異なる場合はどうやっても同じ配列にできない。
その場合は-1。そうでない場合は全て1つにまとめれば、最悪同じにできる。
　
ここからは貪欲法で解く。
先頭から同じ数を作ることができれば、1つにまとめていく。
これを少し言い換えると、A,Bの累積和をそれぞれAA,BBとする。
この時、AA[a]=BB[b]であれば、1つにまとめて同じものにできる。
なので、AA[a]=BB[b]であるペアを前から貪欲に作っていけば、その個数が答えになる。
後はこれの高速化だが、尺取法を使おう。
　
aを[0,N)で全探索する最中にbを[0,M)に動かしていく。
BB[b]＜AA[a]ならばbをインクリメントして、常にAA[a]≦BB[b]が保たれるようにする。
下の答えではbが境界を超えてしまうか判定しているが、最後に番兵を置いてもよさそう。
（BB[M] = inf）

int N, M;
ll A[301010], B[301010];
ll AA[301010], BB[301010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    cin >> M;
    rep(i, 0, M) cin >> B[i];

    AA[0] = A[0];
    rep(i, 1, N) AA[i] = A[i] + AA[i - 1];

    BB[0] = B[0];
    rep(i, 1, M) BB[i] = B[i] + BB[i - 1];

    if (AA[N - 1] != BB[M - 1]) {
        printf("-1\n");
        return;
    }

    int ans = 0;
    int b = 0;
    rep(a, 0, N) {
        while (b < M and BB[b] < AA[a]) b++;
        if (b < M and AA[a] == BB[b]) ans++;
    }

    cout << ans << endl;
}