概要

\(N\) 枚の看板（文字列）を順番に並べ、隣り合う看板同士が重なる部分を最大化して連結したときの、最終的な横断幕の総文字数を求める問題です。ただし、重ね合わせの長さには「どちらの文字列も完全には重なりに含まれない（どちらも少なくとも \(1\) 文字は重なりの外に残る）」という制約があります。

考察

素朴なアプローチとその限界

隣り合う \(2\) つの文字列 \(S_{i-1}\) と \(S_i\) について、重ね合わせられる長さ \(l\) を求めることを考えます。 もし、すべての \(l\)（\(1 \leq l < \min(|S_{i-1}|, |S_i|)\)）について、末尾と先頭が一致するかを愚直に文字比較して調べると、1つのペアに対して最悪で \(O(|S_{i-1}| \times |S_i|)\) の時間がかかってしまいます。 文字列の長さの総和 \(\sum |S_i| \leq 10^6\) という制約があるため、この方法では実行時間制限（TLE）に間に合いません。

したがって、「ある文字列の末尾（接尾辞）」と「別の文字列の先頭（接頭辞）」が一致する最長の高さを高速に求める方法が必要になります。

KMP法（Prefix function）の応用

文字列の一致を高速に判定するアルゴリズムとして、KMP法（Knuth-Morris-Pratt Algorithm）のPrefix function（\(\pi\) 配列）が利用できます。

文字列 \(T\) に対する Prefix function \(\pi[j]\) とは、「\(T\) の先頭 \(j+1\) 文字の部分文字列において、接頭辞（Prefix）と接尾辞（Suffix）が一致する、自身以外の最長の長さ」を表します。

これを利用するために、次のような新しい文字列 \(T\) を構築します。 $\(T = S_i + \text{"\#"} + S_{i-1}\)\( ここで、`#` は \)Si\( や \)S{i-1}$ には含まれない特殊な文字です。

この文字列 \(T\) に対して Prefix function を計算すると、末尾の要素の値 \(\pi[|T|-1]\) は、「\(S_i\) の接頭辞」であり、かつ「\(S_{i-1}\) の接尾辞」である最長の一致長さを直接表すことになります。特殊文字 # を挟んでいるため、一致する長さが \(S_i\) の長さを超えることはありません。

条件「完全には重なりに含まれない」の処理

問題文には「\(l < |S_{i-1}|\) かつ \(l < |S_i|\)」という重要な制約があります。 もし Prefix function で求めた最長の一致長さ \(v = \pi[|T|-1]\) が、この条件を満たさない（すなわち \(v \geq |S_{i-1}|\) または \(v \geq |S_i|\) となる）場合、その重ね合わせは認められません。

この場合、KMP法の性質を利用して、次に長い一致の候補に遡ります。具体的には、条件を満たすまで \(v = \pi[v-1]\) という更新を繰り返します。これにより、条件を満たす範囲での「最長の一致長さ」を高速に見つけることができます。

---

アルゴリズム

各隣接する看板のペア \((S_{i-1}, S_i)\) について、以下の処理を行います。

1. 一時的な文字列の作成: \(T = S_i + \text{"\#"} + S_{i-1}\) を作成します。
2. Prefix function の計算: 文字列 \(T\) に対して、KMP法の \(\pi\) 配列を計算します。
3. 条件を満たす最大長の探索: \(v = \pi[|T|-1]\) とします。 \(v \geq |S_{i-1}|\) または \(v \geq |S_i|\) である間、\(v = \pi[v-1]\) と更新し続けます。
4. 総文字数の更新: 条件を満たした \(v\) が、重ね合わせる長さ \(L_i\) となります。 総文字数に \(|S_i| - L_i\) を加算します。

---

計算量

時間計算量: \(O(\sum_{i=1}^{N} |S_i|)\)

KMP法の Prefix function の計算は、文字列 \(T\) の長さに比例する時間、すなわち \(O(|T|) = O(|S_{i-1}| + |S_i|)\) で動作します。 また、条件を満たすまで \(\pi\) 配列を遡る処理（v = pi[v-1]）も、各ステップで \(v\) が減少するため、全体で線形時間で抑えられます。 すべての看板を連結する処理を合わせても、全体の計算量は文字列の長さの総和に比例する \(O(\sum |S_i|)\) となり、実行時間制限に十分間に合います。

空間計算量: \(O(\sum_{i=1}^{N} |S_i|)\)

すべての文字列を保持する配列、および \(\pi\) 配列のメモリ領域が必要です。これらは最大でも入力文字列の総和に比例するため、空間計算量は \(O(\sum |S_i|)\) となり、メモリ制限にも余裕で収まります。

---

実装のポイント

• 入出力の高速化: C++ では、入力データが大きいため cin.tie(NULL) および ios_base::sync_with_stdio(false) を用いて標準入出力を高速化しています。

• メモリの再利用: 毎ステップで \(\pi\) 配列を新しく確保するとメモリ割り当てのオーバーヘッドが発生するため、vector<int> pi を使い回し、必要に応じて resize することで高速化を図っています。

• 文字列の結合高速化: t += s[i] のように結合する際、あらかじめ reserve を用いて必要なメモリ領域を確保しておくことで、動的なメモリ再確保による無駄なコピーを防いでいます。

  ソースコード

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    // Optimize standard I/O operations for competitive programming
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;

    vector<string> s(n);
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }

    long long total_len = s[0].length();
    vector<int> pi;

    for (int i = 1; i < n; i++) {
        // Construct the string: S_i + "#" + S_{i-1}
        string t;
        t.reserve(s[i].length() + 1 + s[i-1].length());
        t += s[i];
        t += '#';
        t += s[i-1];

        int m = t.length();
        if (pi.size() < m) {
            pi.resize(m);
        }
        
        // Compute the KMP prefix function
        pi[0] = 0;
        for (int j = 1; j < m; j++) {
            int k = pi[j-1];
            while (k > 0 && t[j] != t[k]) {
                k = pi[k-1];
            }
            if (t[j] == t[k]) {
                k++;
            }
            pi[j] = k;
        }

        int v = pi[m-1];
        int len_prev = s[i-1].length();
        int len_curr = s[i].length();
        
        // Enforce the strict condition: overlap length L_i < |S_{i-1}| and L_i < |S_i|
        while (v > 0 && (v >= len_prev || v >= len_curr)) {
            v = pi[v-1];
        }
        
        total_len += (len_curr - v);
    }

    cout << total_len << "\n";

    return 0;
}

---

この解説は gemini-3.5-flash-thinking によって生成されました。