概要

長さ \(N\) の数列 \(C\)（各要素は \(1\)〜\(7\)）から、\(1\)〜\(7\) のすべての値を含む連続部分列 \((l, r)\) の個数を数える問題です。右端 \(r\) を固定したときの「条件を満たす \(l\) の個数」が簡単に求まることに気づけば \(O(N)\) で解けます。

考察

素朴なアプローチ

すべての \((l, r)\) を試して、その区間に \(7\) 種類そろっているかを確認する方法が最初に思い浮かびます。しかし組 \((l,r)\) の個数は約 \(N^2/2 \approx 5 \times 10^{11}\) 個（\(N = 10^6\) のとき）もあり、到底間に合いません。

重要な観察 1：単調性

区間 \([l, r]\) が条件を満たすとき、\(l\) をさらに小さくしても（区間を左に広げても）条件は満たされ続けます。含まれるスタンプの集合は広げると増えるだけなので、\(\{1,\dots,7\}\) を含むという性質は壊れません。

したがって右端 \(r\) を固定すると、条件を満たす \(l\) は

\[1 \le l \le L(r)\]

という形の連続した範囲になります（\(L(r)\) は条件を満たす最大の \(l\)、存在しなければ \(0\) 個）。つまり右端 \(r\) に対する答えは ちょうど \(L(r)\) 個です。

重要な観察 2：\(L(r)\) の正体

区間 \([l, r]\) が種類 \(k\) を含む条件は、「\(r\) 以下で最後に種類 \(k\) が現れた位置」を \(\mathrm{last}[k]\) とすると

\[l \le \mathrm{last}[k]\]

です（\(\mathrm{last}[k]\) がまだ存在しない場合は絶対に含められません）。これを \(k = 1, \dots, 7\) すべてについて満たす必要があるので

\[L(r) = \min_{1 \le k \le 7} \mathrm{last}[k]\]

となります。\(\mathrm{last}[k]\) を「まだ出ていない場合は \(0\)」と初期化しておけば、最小値が \(0\) のときは「まだ 7 種類そろっていない → 0 個」と自動的に処理できて便利です。

なお \(C_i \in \{1,\dots,7\}\) なので、「\(7\) 種類すべてを含む」ことと「集合が \(\{1,\dots,7\}\) と一致する」ことは同じです（余計な値が入り込む心配がない）。

具体例

\(N = 8\), \(C = (1,2,3,4,5,6,7,1)\) のとき

• \(r = 1 \dots 6\)：まだ 7 種類そろっていない（どこかの \(\mathrm{last}\) が \(0\)）→ \(0\) 個
• \(r = 7\)：\(\mathrm{last} = (1,2,3,4,5,6,7)\)、最小は \(1\) → \(1\) 個（\((1,7)\)）
• \(r = 8\)：\(\mathrm{last}[1] = 8\) に更新され \(\mathrm{last} = (8,2,3,4,5,6,7)\)、最小は \(2\) → \(2\) 個（\((1,8), (2,8)\)）

合計 \(3\) 個で、確かに \((1,7), (1,8), (2,8)\) の \(3\) つが答えです。

アルゴリズム

1. 長さ \(8\) の配列 last を \(0\) で初期化する（インデックス \(1\)〜\(7\) を使う）。
2. \(i = 1, 2, \dots, N\) の順に見て
   • last[C_i] = i と更新する。
   • \(m = \min(\mathrm{last}[1], \dots, \mathrm{last}[7])\) を計算する。
   • 答えに \(m\) を加算する（\(m = 0\) なら加算なしと同じ）。
3. 合計を出力する。

「尺取り法（two pointers）」で各種類の出現回数を管理しながら左端を進める解法でも同じ計算量で解けますが、種類数がたかだか \(7\) と小さいので、上記の「最後に出た位置の最小値」を毎回取り直す方法がシンプルです。

計算量

• 時間計算量: \(O(7N) = O(N)\)
• 空間計算量: \(O(1)\)（入力の保持を除く。定数サイズの配列 last のみ）

実装のポイント

• 答えの大きさ：最大で \(O(N^2)\) 程度（\(5 \times 10^{11}\) 規模）になるため、C++ などでは long long を使う必要があります。Python では多倍長整数なので問題ありません。

• 入力の高速読み込み：\(N \le 10^6\) なので、Python では input() を繰り返すのではなく sys.stdin.buffer.read().split() で一括読み込みします。さらに、全要素を先に int のリストへ変換せず、ループ内で必要な要素だけ int(data[i]) するとメモリと時間を節約できます。

• min() の呼び出しを避ける：要素数 \(7\) の min(last[1:8]) を毎回呼ぶとスライス生成と関数呼び出しのオーバーヘッドが \(10^6\) 回分かかります。コードのように比較を手で展開（アンロール）しておくと Python でも十分高速に動きます。

• 未出現を \(0\) で表現する：last を \(0\) 初期化しておくことで、「まだ 7 種類そろっていない → 最小値が \(0\) → 加算しない」と場合分けを最小限にできます（位置を \(1\)-indexed にしている点が効いています）。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    last = [0] * 8
    ans = 0
    for i in range(1, n + 1):
        last[int(data[i])] = i
        m = last[1]
        t = last[2]
        if t < m: m = t
        t = last[3]
        if t < m: m = t
        t = last[4]
        if t < m: m = t
        t = last[5]
        if t < m: m = t
        t = last[6]
        if t < m: m = t
        t = last[7]
        if t < m: m = t
        if m:
            ans += m
    sys.stdout.write(str(ans) + "\n")

main()

---

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