概要

長さ \(N\) の数列 \(C\)（各要素は \(1\) 以上 \(7\) 以下）に対して、区間 \([l, r]\) に \(1\) から \(7\) のすべての値が現れるような組 \((l, r)\) の個数を数える問題です。いわゆる「尺取り法（two pointers）」の典型問題です。

考察

素朴なアプローチ

すべての \((l, r)\) を試すと \(O(N^2)\) 通りあり、\(N \le 10^6\) では \(10^{12}\) 通りにもなるので当然間に合いません。区間ごとに種類を数えると更に遅くなります。

重要な観察 1：単調性

区間を右に延ばす（\(r\) を増やす）と、含まれるスタンプの種類は増えるだけで減りません。同様に、区間を左に延ばす（\(l\) を減らす）と種類は増えるだけです。

したがって \(r\) を固定したとき、 - \([l, r]\) が条件を満たす（全 \(7\) 種類含む）なら、\(l' \le l\) なる任意の \(l'\) でも \([l', r]\) は条件を満たす

が成り立ちます。つまり条件を満たす \(l\) の集合は \(1, 2, \dots, f(r)\) というプレフィックスの形になります（\(f(r)\) は条件を満たす最大の \(l\)、存在しなければ \(f(r) = 0\)）。

よって答えは $\(\text{ans} = \sum_{r=1}^{N} f(r)\)\( と書けます。あとは各 \)r\( について \)f®$ を高速に求めればよいです。

重要な観察 2：\(f(r)\) の単調性

\(r\) が増えると条件は緩くなるので、\(f(r)\) は単調非減少です（\(f(1) \le f(2) \le \dots \le f(N)\)）。したがって左端 \(l\) を巻き戻す必要がなく、\(l\) を一方向に動かすだけで全ての \(r\) について \(f(r)\) を求められます。これが尺取り法です。

具体例：\(C = (1, 1, 2, 3, 4, 5, 6, 7)\) のとき - \(r = 7\) まではまだ \(7\) が出ていないので \(f(r) = 0\) - \(r = 8\)：区間 \([2, 8]\) に全種類が含まれ、\([3, 8]\) には \(1\) が含まれないので \(f(8) = 2\)

よって答えは \(2\)（\((1,8)\) と \((2,8)\)）です。

アルゴリズム

窓 \([l, r]\) の中の各種類の出現回数 cnt[1..7] と、出現している種類数 distinct を持ちます。

\(r = 1, 2, \dots, N\) の順に以下を行います。

1. \(C_r\) を窓に追加する。追加前に cnt[C_r] == 0 だったら distinct を \(1\) 増やす。
2. 窓の左端を、含まれる種類の集合を変えない限界まで縮める：cnt[C_l] > 1 である間、cnt[C_l]-- して l++。
   • ループ終了時は cnt[C_l] == 1、すなわち左端の要素は窓内で唯一の出現です。これ以上縮めると種類が \(1\) つ減ってしまうので、\(l\) は「種類集合を保つ最大の左端」になっています。
   • この縮小操作は種類を減らさないので、distinct は一度 \(7\) になったらそのまま \(7\) を保ちます。
3. distinct == 7 なら、この \(l\) がまさに \(f(r)\) なので、ans += l（左端の候補は \(1, 2, \dots, l\) の \(l\) 通り）。

ポイントは「distinct == 7 かどうかを見るのではなく、常に種類集合を保つ最大の \(l\)」を維持している点です。こうすると条件分岐がシンプルになります。

（別解として、各種類 \(v\) の「\(r\) 以下での最後の出現位置」\(\mathrm{last}[v]\) を持ち、\(f(r) = \min_{v=1}^{7} \mathrm{last}[v]\)（どれかが \(0\) なら \(0\)）として求める方法もあります。\(7\) 種類しかないので毎回 \(\min\) を取っても \(O(7N)\) で十分高速です。）

計算量

• 時間計算量: \(O(N)\)（\(l\) は全体を通して単調に増えるだけなので、内側の while ループの総回数は \(N\) 以下）
• 空間計算量: \(O(N)\)（数列の保持。\(C\) を読みながら処理すれば \(O(1)\) でも可能）

実装のポイント

• オーバーフロー：答えは最大で \(O(N^2)\)、具体的には \(10^{12}\) 程度になり得るので、\(32\) ビット整数では溢れます。long long を使い、ans += (long long)l; のようにキャストしてください（Python なら気にする必要はありません）。

• 入力の高速化：\(N \le 10^6\) なので入力が大きめです。C++ では scanf や、cin を使うなら ios::sync_with_stdio(false); cin.tie(nullptr); を忘れないようにしましょう。

• 添字：cnt は種類 \(1\)〜\(7\) を使うのでサイズ \(8\) の配列にして \(0\) 番目を使わないようにすると楽です。

• while の条件：l <= r を条件に含めておくと安全です（実際には窓が空になる前に cnt[C_l] == 1 で止まりますが、境界を明示しておくと安心です）。

• 全 \(7\) 種類が一度も揃わない場合は distinct が \(7\) にならず ans は \(0\) のままになり、正しく処理されます。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    if(scanf("%d",&n)!=1) return 0;
    vector<int> c(n+1);
    for(int i=1;i<=n;i++) scanf("%d",&c[i]);
    long long ans=0;
    int cnt[8]={0};
    int distinct=0;
    int l=1;
    for(int r=1;r<=n;r++){
        if(cnt[c[r]]++==0) distinct++;
        while(l<=r && cnt[c[l]]>1){
            cnt[c[l]]--;
            l++;
        }
        if(distinct==7) ans += (long long)l;
    }
    printf("%lld\n", ans);
    return 0;
}

---

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