概要

\(1\) から \(7\) までの整数で表されるスタンプが並んだ長さ \(N\) の列から、全 \(7\) 種類すべてが含まれる連続区間 \([l, r]\) の総数を求める問題です。

考察

素朴なアプローチとその問題点

すべての区間の組 \((l, r)\) (\(1 \le l \le r \le N\)) を列挙して、その中に \(1\) から \(7\) がすべて含まれるかを確認する方法が考えられます。 しかし、区間の選び方だけでも \(\frac{N(N+1)}{2}\) 通り（\(O(N^2)\) 通り）存在します。本問では \(N \le 10^6\) であるため、区間の総数は約 \(5 \times 10^{11}\) にも達し、制限時間内に到底終わりません（TLE）。

右端 \(r\) を固定して考える

効率的に数え上げるために、区間の右端 \(r\) を \(1\) から \(N\) まで順に固定して考えます。

右端を \(r\) に固定したとき、左端 \(l\) (\(1 \le l \le r\)) として選べる条件を整理してみましょう。 区間 \([l, r]\) に種類 \(k\) (\(1 \le k \le 7\)) のスタンプが含まれるためには、「\(r\) 以前で種類 \(k\) が最後に現れた位置」が \(l\) 以上である必要があります。

したがって、すべての種類 \(1 \le k \le 7\) が区間 \([l, r]\) に含まれる条件は、各種類 \(k\) の最新の出現位置を \(P_k\) と置くと、 $\(l \le P_1 \text{ かつ } l \le P_2 \text{ かつ } \dots \text{ かつ } l \le P_7\)$ が成り立つことです。

これは、最新出現位置の最小値を \(M = \min(P_1, P_2, \dots, P_7)\) と置くと、 $\(1 \le l \le M\)$ と言い換えることができます。

つまり、右端が \(r\) のときに条件を満たす左端 \(l\) の個数は、ちょうど \(M\) 個になります。 なお、まだ一度も出現していないスタンプ種類がある場合は、その種類の最新位置を \(0\) とみなせば \(M = 0\) となり、条件を満たす \(l\) が \(0\) 個であることが自然に表現できます。

アルゴリズム

1. 各スタンプ種類 \(1 \dots 7\) の直近の出現位置を保持する配列 last_pos を用意し、初期値をすべて \(0\) とします。
2. 答えの合計を保持する変数 ans を \(0\) で初期化します。
3. \(r = 1, 2, \dots, N\) について、順番に以下の処理を行います：
   • \(C_r\) の最新の出現位置を \(r\) に更新します（last_pos[C_r] = r）。
   • 全種類について直近の出現位置の最小値 \(M = \min_{1 \le i \le 7} \text{last\_pos}[i]\) を求めます。
   • ans に \(M\) を加算します。
4. 最終的な ans の値を出力します。

計算量

• 時間計算量: \(O(NK)\) （\(K\) はスタンプの種類数で、今回は \(K = 7\)）
  • \(r\) を \(1\) から \(N\) まで動かし、各ステップで要素数 \(7\) の配列の最小値を求めるため、ステップごとの計算量は \(O(K)\) です。全体では \(O(7N)\) となり、約 \(7 \times 10^6\) 回の計算で十分に高速に動作します。
• 空間計算量: \(O(K)\)
  • 大きさ \(8\) の配列 last_pos といくつかの変数のみを保持すればよいため、\(O(1)\) です。

実装のポイント

• オーバーフローへの注意: 条件を満たす区間の総数は、最大で約 \(\frac{N(N+1)}{2} \approx 5 \times 10^{11}\) になります。これは一般的な 32 bit 整数型（上限約 \(2 \times 10^9\)）を超えてオーバーフローするため、答えを足し合わせる変数 ans は 64 bit 整数型（C++ の long long 型）を使用する必要があります。

• 出現していない種類の扱い: last_pos の初期値を \(0\) にしておくことで、「全種類揃っていないときは最小値が \(0\) になり、答えに \(0\) が足される（＝条件を満たす区間が存在しない）」という処理を、条件分岐を書かずにシンプルに扱うことができます。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    vector<int> last_pos(8, 0);
    long long ans = 0;

    for (int r = 1; r <= n; ++r) {
        int c;
        cin >> c;
        last_pos[c] = r;

        int min_pos = r;
        for (int i = 1; i <= 7; ++i) {
            min_pos = min(min_pos, last_pos[i]);
        }
        ans += min_pos;
    }

    cout << ans << "\n";

    return 0;
}

---

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