本記事では、与えられた2つのデータブロック列から、内容が同一であると想定されるファイルの最大数を特定するアルゴリズムについて解説します。各データブロック列は、特定の順序で転送されたファイルの集合を暗号化したものと見なされます。ここでいう「ファイル」とは、連続する1つ以上のデータブロックの集まりであり、その合計サイズがファイルサイズに相当します。2つのデータブロック列が同じアーカイブ（ファイル集合）を構成している場合、それぞれのファイルは異なる数のブロックに分割されて転送される可能性がありますが、ファイルの順序と各ファイルの合計サイズは一致します。

問題定義 2つのデータストリームが与えられます。1つ目のストリームは $n$ 個のブロックからなり、各ブロックのサイズは $x_1, x_2, \ldots, x_n$ です。2つ目のストリームは $m$ 個のブロックからなり、各ブロックのサイズは $y_1, y_2, \ldots, y_m$ です。 これらのデータストリームを、対応するセグメントの合計サイズが等しくなるような連続した「ファイル」に分割します。例えば、1つ目のストリームの最初のファイルが $x_1, \ldots, x_a$ で構成され、2つ目のストリームの最初のファイルが $y_1, \ldots, y_b$ で構成される場合、これらのブロックの合計サイズ $x_1+\ldots+x_a$ と $y_1+\ldots+y_b$ は等しくなければなりません。同様に、2つ目のファイル以降もこの条件を満たす必要があります。 この条件を満たす最大のファイル数（共通セグメント数）を求めます。

入力形式

• 最初の行に、1つ目のデータストリームのブロック数 $n$ と2つ目のデータストリームのブロック数 $m$ ( $1 \le n, m \le 10^5$ ) が与えられます。
• 次の行に、1つ目のデータストリームを構成する $n$ 個のブロックサイズ $x_1, x_2, \ldots, x_n$ ( $1 \le x_i \le 10^6$ ) が与えられます。
• その次の行に、2つ目のデータストリームを構成する $m$ 個のブロックサイズ $y_1, y_2, \ldots, y_m$ ( $1 \le y_i \le 10^6$ ) が与えられます。 保証事項：1つ目のデータストリームの全ブロックサイズの合計と、2つ目のデータストリームの全ブロックサイズの合計は等しいです。また、その合計サイズは $10^6$ 以下です。

出力形式 共通するファイルの最大数を整数で出力します。

解決策: 累積和と二点探索 (Two Pointers)

1. 累積和の計算 各データストリームについて、先頭からのブロックサイズの累積和を計算します。これにより、任意の連続するブロックの合計サイズを $O(1)$ で求めることができます。たとえば、配列 $A$ の累積和配列 $S$ を $S[k] = \sum_{i=1}^{k} A[i]$ と定義すると、区間 $[p, q]$ の合計は $S[q] - S[p-1]$ で計算できます。 この問題では、特定のインデックスまでの累積和がファイル全体のサイズに相当するため、各ストリームの累積和配列 $C_1$ と $C_2$ を以下のように作成します。

• $C_1[k]$: 1つ目のストリームの先頭から $k$ 個のブロックの合計サイズ。
• $C_2[k]$: 2つ目のストリームの先頭から $k$ 個のブロックの合計サイズ。 これらの累積和配列は、それぞれ単調非減少（値が増加するか、同じままである）です。

2. 二点探索による共通セグメントの検出 2つの累積和配列 $C_1$ と $C_2$ を利用して、共通のセグメントの終了点を効率的に見つけます。これは「二点探索（Two Pointers）」または「尺取り法」と呼ばれる手法で解決できます。 1つ目のストリームの累積和配列 $C_1$ をインデックス $i$ で走査し、同時に2つ目のストリームの累積和配列 $C_2$ をインデックス $j$ で走査します。共通のセグメントが見つかるたびにカウンターを増やします。
3. $C_1$ のインデックス $i$ を1から $n$ まで進めます。
4. 各 $i$ について、$C_2$ のインデックス $j$ を、現在の $j$ の位置から $C_2[j] \ge C_1[i]$ となるまで進めます。このとき、$j$ は決して後戻りせず、常に前進します（これは累積和配列が単調非減少であるため可能です）。
5. もし $C_2[j] = C_1[i]$ であれば、これは両方のストリームで同じサイズのセグメントが終了したことを意味します。共通セグメントの数を1つ増やします。
6. $i$ が $n$ に達したら処理を終了し、カウントした共通セグメント数を出力します。 このアルゴリズムは、各累積和配列を一度ずつしか走査しないため、時間計算量は $O(N+M)$ となり、効率的です。

C++による実装例 以下に、累積和と二点探索を用いたC++のコード例を示します。ブロック数は最大 $10^5$、各ブロックのサイズは最大 $10^6$ ですが、合計サイズも最大 $10^6$ なので、個々のブロックサイズは $int$ で十分です。しかし、累積和は最大 $10^6$ になるため、$long long$ を使用しても安全です（今回の制約では $int$ でも問題ありません）。

#include <iostream> // 標準入出力のために必要
#include <vector>   // 動的配列std::vectorを使用するために必要
#include <numeric>  // std::accumulate など、数値演算に関するユーティリティだが、ここでは直接は使わない

// 主処理を行う関数
void solve() {
    int n, m; // 各データストリームのブロック数
    std::cin >> n >> m;

    // 1つ目のデータストリームのブロックサイズを格納
    // vector<long long> stream1Blocks(n); // 個々のブロックサイズはintで十分だが、汎用性を考慮
    std::vector<long long> cumulativeSums1(n + 1, 0); // 累積和を格納 (0-indexed blocks, 1-indexed sums)
    for (int i = 0; i < n; ++i) {
        long long blockSize; // ブロックサイズを一時的に読み込む
        std::cin >> blockSize;
        // cumulativeSums1[k] は先頭からk個のブロックの合計サイズを表す
        cumulativeSums1[i + 1] = cumulativeSums1[i] + blockSize;
    }

    // 2つ目のデータストリームのブロックサイズを格納
    // vector<long long> stream2Blocks(m);
    std::vector<long long> cumulativeSums2(m + 1, 0); // 累積和を格納
    for (int i = 0; i < m; ++i) {
        long long blockSize;
        std::cin >> blockSize;
        cumulativeSums2[i + 1] = cumulativeSums2[i] + blockSize;
    }

    int commonSegmentCount = 0; // 共通セグメントの数
    int stream2Pointer = 1;     // cumulativeSums2を参照するためのポインタ（1-basedインデックス）

    // 1つ目のストリームの累積和を順に走査 (インデックス1からnまで)
    for (int i = 1; i <= n; ++i) {
        // stream2Pointerを進め、cumulativeSums2[stream2Pointer] が cumulativeSums1[i] 以上になるまで
        // もし stream1 の現在の累積和 (cumulativeSums1[i]) より stream2 の累積和 (cumulativeSums2[stream2Pointer]) が小さい場合、
        // stream2 のポインタを進めて追いつかせる
        while (stream2Pointer <= m && cumulativeSums2[stream2Pointer] < cumulativeSums1[i]) {
            stream2Pointer++;
        }

        // stream2Pointer が範囲内で、かつ累積和が一致する場合、共通セグメントが見つかった
        if (stream2Pointer <= m && cumulativeSums1[i] == cumulativeSums2[stream2Pointer]) {
            commonSegmentCount++; // 共通セグメント数をインクリメント
        }
        // stream2Pointer が範囲外になった、または cumulativeSums2[stream2Pointer] が cumulativeSums1[i] を超過した場合、
        // 現在の cumulativeSums1[i] に対応する共通セグメントは存在しない。
        // ただし、stream2Pointer は次の i でもその位置から探索を始めるため効率的。
    }

    // 結果を出力
    std::cout << commonSegmentCount << std::endl;
}

int main() {
    // 高速I/O設定 (競技プログラミングでよく使われる手法)
    std::ios_base::sync_with_stdio(false); // C標準I/Oとの同期を無効化
    std::cin.tie(NULL);                   // cinとcoutの結合を解除

    solve(); // 問題解決関数を呼び出す
    return 0; // 正常終了
}

実行例 サンプル 1 入力:

7 6
2 5 3 1 11 4 4
7 8 2 4 1 8

出力:

3

解説: この例では、3つの共通ファイルセグメントが見つかります。例えば、サイズ7 ($2+5$ と $7$)、サイズ15 ($3+1+11$ と $8+2+4+1$)、サイズ8 ($4+4$ と $8$)。

サンプル 2 入力:

3 3
1 10 100
1 100 10

出力:

2

解説: サイズ1 ($1$ と $1$)、サイズ110 ($10+100$ と $100+10$) の2つのセグメントが見つかります。