概要

\(1\) から \(7\) までの数値からなる長さ \(N\) の数列において、全 \(7\) 種類の数値をすべて含む連続部分列 \([l, r]\) の個数を求める問題です。

考察

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

すべての区間 \([l, r]\) (\(1 \le l \le r \le N\)) の組み合わせを全探索することを考えてみます。 区間の選び方は全部で \(\frac{N(N+1)}{2}\) 通り存在します。本問題の制約は \(N \le 10^6\) であるため、区間の総数は約 \(5 \times 10^{11}\) 通りとなり、すべての区間を調べていては実行時間制限に到底間に合いません（TLEとなります）。したがって、より効率的なアプローチが必要です。

右端を固定して考える

効率化の定石として、「区間の右端 \(r\) を固定したときに、条件を満たす左端 \(l\) が何個あるか」を考えます。

右端を \(r\) と決めたとき、区間 \([l, r]\) にスタンプ種類 \(k\) (\(1 \le k \le 7\)) が含まれる条件は何でしょうか？ それは、「\(r\) 以下の位置にあるスタンプ \(k\) のうち、最も右側（直近）のインデックス」を \(last_k\) としたとき、\(l \le last_k\) が成り立つことです。

すべてのスタンプ \(1 \sim 7\) が区間 \([l, r]\) に含まれるためには、すべての \(k\) について \(l \le last_k\) が成り立つ必要があります。 すなわち、 $\(l \le \min(last_1, last_2, last_3, last_4, last_5, last_6, last_7)\)$ であれば良いことが分かります。

具体例

例えば、右端 \(r\) まで見た時点で各スタンプが最後に出現した位置が以下のようだったとします： - \(last_1 = 8, last_2 = 12, last_3 = 5, last_4 = 9, last_5 = 15, last_6 = 7, last_7 = 11\)

このときの最小値は \(last_3 = 5\) です。 この場合、\(l \le 5\) を満たす \(l\)、すなわち \(l = 1, 2, 3, 4, 5\) の \(5\) 通りについて、区間 \([l, r]\) にすべてのスタンプが含まれます（\(l \ge 6\) にしてしまうと、スタンプ \(3\) が区間から外れてしまいます）。 このように、最小値を \(m\) とすると、右端 \(r\) に対する有効な左端 \(l\) の個数はちょうど \(m\) 個になります。

なお、まだ一度も出現していないスタンプがある場合は、その \(last\) を \(0\) としておけば、最小値 \(m\) は \(0\) となり、「条件を満たす \(l\) は \(0\) 個」として正しく扱うことができます。

アルゴリズム

1. 各スタンプ \(1 \sim 7\) の直近の出現位置を記録する変数 \(last_1, \dots, last_7\) をすべて \(0\) で初期化します。
2. 答えのカウンター ans を \(0\) で初期化します。
3. \(r = 1\) から \(N\) まで順に見ていきます：
   • スタンプ \(C_r\) の直近の出現位置を \(r\) に更新します (\(last_{C_r} = r\))。
   • \(7\) 種類の直近位置の最小値 \(m = \min(last_1, \dots, last_7)\) を計算します。
   • ans に \(m\) を加算します。
4. 最終的な ans を出力します。

計算量

• 時間計算量: \(O(N)\)
  • \(r\) を \(1\) から \(N\) まで \(1\) ずつ進めるループが \(N\) 回回ります。各ステップで行う更新および \(7\) 個の値の最小値計算は \(O(1)\) なので、全体で \(O(N)\) となり十分に高速です。
• 空間計算量: \(O(N)\)
  • 入力数列 \(C\) を保持するために \(O(N)\) のメモリを使用します（変数自体は定数個です）。

実装のポイント

• 答えのオーバーフロー:

  • 条件を満たすペアの総数は最大で約 \(\frac{N(N+1)}{2} \approx 5 \times 10^{11}\) に達するため、32 bit 整数型には収まりません。C++ などでは 64 bit 整数型（long long）を使用する必要があります（Python では自動的に多倍長整数として扱われるためオーバーフローの心配はありません）。

• 高速な入出力:

  • \(N \le 10^6\) と入力サイズが大きいため、Python では sys.stdin.read().split() を使用して一括で入力を読み込むことで、実行時間を大幅に短縮できます。

    ソースコード

import sys


def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    C = [int(x) for x in input_data[1:]]

    l1 = l2 = l3 = l4 = l5 = l6 = l7 = 0
    ans = 0

    for i in range(1, N + 1):
        x = C[i - 1]
        if x == 1:
            l1 = i
        elif x == 2:
            l2 = i
        elif x == 3:
            l3 = i
        elif x == 4:
            l4 = i
        elif x == 5:
            l5 = i
        elif x == 6:
            l6 = i
        else:
            l7 = i

        m = l1
        if l2 < m:
            m = l2
        if l3 < m:
            m = l3
        if l4 < m:
            m = l4
        if l5 < m:
            m = l5
        if l6 < m:
            m = l6
        if l7 < m:
            m = l7

        ans += m

    print(ans)


if __name__ == "__main__":
    main()

---

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