概要

連続する区間のうち、全 \(7\) 種類のスタンプを含むものの個数を求めます。区間の右端を固定し、各種類が最後に現れた位置から、条件を満たす左端の個数を数えます。

考察

すべての区間を調べると間に合わない

区間 \((l,r)\) の候補は全部で \(\frac{N(N+1)}{2}\) 個あります。左端ごとに右端を伸ばしながらスタンプの種類を管理しても、時間計算量は \(O(N^2)\) です。

\(N\) は最大 \(10^6\) なので、区間を一つずつ調べる方法では間に合いません。

右端を固定し、各種類の「最後の出現位置」を考える

右端 \(r\) を固定します。チェックポイント \(1\) から \(r\) までの中で、種類 \(s\) が最後に現れた位置を \(\mathrm{last}[s]\) とします。まだ現れていない種類については、\(\mathrm{last}[s]=0\) とします。

区間 \([l,r]\) に種類 \(s\) が含まれる条件は、次のとおりです。

\(l \le \mathrm{last}[s]\)

実際、最後の出現位置が \(l\) 以上なら、その位置は区間内にあります。逆に、その位置が \(l\) 未満なら、種類 \(s\) は区間内にはありません。

したがって、全 \(7\) 種類が含まれるための必要十分条件は、

\(l \le \min(\mathrm{last}[1],\mathrm{last}[2],\dots,\mathrm{last}[7])\)

です。この最小値を \(m\) とすると、条件を満たす左端は \(1,2,\dots,m\) の ちょうど \(m\) 個 になります。

まだ現れていない種類がある場合は \(m=0\) となり、条件を満たす区間がないことも自然に表せます。

具体例

スタンプの列が次のようになっているとします。

\(1,2,3,4,5,6,7,1\)

右端が \(r=7\) のとき、各種類の最後の出現位置は、

\((1,2,3,4,5,6,7)\)

です。最小値は \(1\) なので、有効な区間は \([1,7]\) の \(1\) 個です。

右端が \(r=8\) になると、種類 \(1\) の最後の出現位置だけが更新され、

\((8,2,3,4,5,6,7)\)

となります。最小値は \(2\) なので、有効な区間は \([1,8]\) と \([2,8]\) の \(2\) 個です。

このように、右端ごとの個数を足し合わせれば、すべての有効な区間を重複なく数えられます。

アルゴリズム

1. 各種類の最後の出現位置を管理する配列 last を、すべて \(0\) で初期化します。
2. 答えを格納する変数 answer を \(0\) にします。
3. 右端 \(r\) を \(1\) から \(N\) まで順に動かし、次の処理を行います。
   • スタンプの種類 \(C_r\) を読み込みます。
   • 種類 \(C_r\) の最後の出現位置を \(r\) に更新します。
   • last の最小値を answer に加算します。
4. answer を出力します。

各右端について、条件を満たす左端の個数を正確に加算しています。また、各区間の右端は一意なので、数え漏れも重複もありません。

計算量

• 時間計算量: \(O(7N)=O(N)\)
  各チェックポイントで、長さ \(7\) の配列の最小値を求めます。
• 空間計算量: \(O(7)=O(1)\)
  各種類の最後の出現位置だけを保持し、入力列全体を保存する必要はありません。

実装のポイント

• チェックポイントの位置は \(1\) 始まりにします。
  これにより、初期値の \(0\) を「まだ現れていない」という意味で使えます。array<int, 7> last{}; は全要素を \(0\) で初期化します。

• スタンプの種類と配列の添字を対応させます。
  種類は \(1\) から \(7\)、配列の添字は \(0\) から \(6\) なので、種類 c の更新は last[c - 1] = r; とします。

• 最後の出現位置を更新してから最小値を加算します。
  右端 \(r\) のスタンプも含めた状態で、区間の個数を数えるためです。

• 答えには 64 bit 整数型を使います。
  区間の総数は最大で \(\frac{N(N+1)}{2}\) 個あり、答えが 32 bit 整数型に収まらない場合があります。提示コードでは long long を使用しています。

  ソースコード

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

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

    int N;
    cin >> N;

    array<int, 7> last{};
    long long answer = 0;

    for (int r = 1; r <= N; ++r) {
        int c;
        cin >> c;
        last[c - 1] = r;
        answer += *min_element(last.begin(), last.end());
    }

    cout << answer << '\n';
    return 0;
}

---

この解説は gpt-6-astra-medium によって生成されました。