概要

この問題は、長さ \(N\) の文字列 \(S\) の中から、互いに重なり合わないように長さ \(M\) の特定のパターン \(T\) を最大で何個選択できるかを求め、それをもとに最小の合計所要時間を計算する問題です。

考察

1. 数式の整理

割引パスを適用した区間の数を \(k\) としたとき、合計所要時間は \(N - k(M - 1)\) と表されます。 \(N\) と \(M\) は入力で与えられる定数であるため、合計所要時間を最小化するためには、割引パスを適用する区間の数 \(k\) を最大化することに帰着されます。

2. 素朴なアプローチと課題

\(S\) の中から \(T\) と一致する箇所をすべて探し、それらが重ならないように最大個数を選択する必要があります。

文字列 \(S\) の各位置から \(T\) と一致するかどうかを愚直に判定すると、1回の判定に最大 \(O(M)\) かかります。すべての開始位置について判定を行うと、全体で \(O(NM)\) の計算量が必要になります。 今回の制約は \(N, M \leq 10^6\) であるため、最悪の場合に \(10^{12}\) 回程度の計算が発生し、実行時間制限（通常 2 秒程度）に間に合わず TLE（実行時間制限超過） になってしまいます。

3. 高速な解決策

この課題を解決するために、以下の2つのステップに分けて処理を高速化します。

1. 文字列検索の高速化: \(S\) の中から \(T\) が出現するすべての開始位置を \(O(N + M)\) で列挙できるKMP法（Knuth-Morris-Pratt Algorithm）を使用します。
2. 区間の最大化（区間スケジューリング問題）: 列挙された出現位置から、重ならないように区間を最大個数選択します。これは「区間スケジューリング問題」として知られており、貪欲法（Greedy Algorithm）を用いることで \(O(N)\) で最適解を求めることができます。今回の区間はすべて長さ \(M\) で等しいため、左側（開始インデックスが小さい順）から順番に、重ならないものを貪欲に選んでいくだけで最大個数が得られます。

---

アルゴリズム

ステップ 1: KMP法によるパターン検索

KMP法は、パターンの「接頭辞と接尾辞が一致する長さ」をあらかじめ計算（LPS配列の構築）しておくことで、マッチングに失敗した際に無駄な比較をスキップするアルゴリズムです。 これを用いて、文字列 \(S\) の中で \(T\) が出現するすべての開始インデックスを昇順にリスト matches に格納します。

ステップ 2: 貪欲法による区間選択

得られた matches を用いて、重ならない区間の最大数 \(k\) を求めます。

1. 最後に選択した区間の終了インデックスを保持する変数 last_end を \(-1\) で初期化します。
2. matches に含まれる開始インデックス idx を順番に見ていきます。
3. もし idx > last_end ならば、その区間はこれまでに選択した区間と重なりません。
   • 区間の数 \(k\) を \(1\) 増やします。
   • last_end を、新しく選択した区間の末尾のインデックスである idx + M - 1 に更新します。
4. 重なる場合は、その区間を無視して次のインデックスに進みます。

ステップ 3: 最小所要時間の計算

求まった最大区間数 \(k\) を用いて、最終的な答え \(N - k(M - 1)\) を計算して出力します。

---

計算量

• 時間計算量: \(O(N + M)\)

  • KMP法のLPS配列構築に \(O(M)\)、検索処理に \(O(N)\) かかります。
  • 貪欲法による区間選択は、マッチング件数（最大でも \(N\) 件）に対して1重のループで処理するため \(O(N)\) です。
  • したがって、全体の時間計算量は \(O(N + M)\) となり、制約の \(10^6\) に対して十分高速に動作します。

• 空間計算量: \(O(N + M)\)

  • KMP法のLPS配列に \(O(M)\)、マッチング位置を記録する配列に最大 \(O(N)\) のメモリを使用します。

---

実装のポイント

• \(M > N\) のコーナーケース: 割引パスの長さ \(M\) が高速道路の長さ \(N\) より大きい場合、割引パスを適用できる区間は存在しません。この場合は探索を行う必要はなく、即座に \(N\) を出力して終了します。

• 高速入出力: \(N\) の値が大きいため、C++では std::cin と std::cout の同期を切る（ios_base::sync_with_stdio(false); cin.tie(NULL);）ことで、入出力にかかる時間を短縮しています。

  ソースコード

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

using namespace std;

// Function to build the Longest Prefix Suffix (LPS) array for KMP
vector<int> buildLPS(const string& pat) {
    int m = pat.length();
    vector<int> lps(m, 0);
    int len = 0;
    int i = 1;
    while (i < m) {
        if (pat[i] == pat[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}

// KMP algorithm to find all starting indices of pattern in text
vector<int> kmpSearch(const string& pat, const string& txt) {
    int m = pat.length();
    int n = txt.length();
    vector<int> lps = buildLPS(pat);
    vector<int> matches;
    int i = 0; // index for txt
    int j = 0; // index for pat
    while (i < n) {
        if (pat[j] == txt[i]) {
            j++;
            i++;
        }
        if (j == m) {
            matches.push_back(i - j);
            j = lps[j - 1];
        } else if (i < n && pat[j] != txt[i]) {
            if (j != 0)
                j = lps[j - 1];
            else
                i++;
        }
    }
    return matches;
}

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

    int N, M;
    if (!(cin >> N >> M)) return 0;

    string S, T;
    cin >> S >> T;

    if (M > N) {
        cout << N << "\n";
        return 0;
    }

    // Find all occurrences of T in S
    vector<int> matches = kmpSearch(T, S);

    // Greedy interval scheduling to find the maximum number of non-overlapping intervals
    long long k = 0;
    int last_end = -1;
    for (int idx : matches) {
        if (idx > last_end) {
            k++;
            last_end = idx + M - 1;
        }
    }

    // Calculate the minimum total time
    long long ans = (long long)N - k * (M - 1);
    cout << ans << "\n";

    return 0;
}

---

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