AtCoder ARC 022 B - 細長いお菓子 (試験管水色)

しゃくとり法のいい練習問題！！

• 問題へのリンク

問題概要

長さ の正の整数列 が与えられる。

整数列の連続する部分列のうち、「同じ数値が 2 箇所以上登場しない」という条件を満たす最大長を求めよ。

制約

• 
• 

考えたこと

今回の問題には、次のような著しい構造がある！！！

---

区間 が条件を満たすならば、区間 に包含される任意の区間も条件を満たす。

---

このような「単調性」に関する構造があったら、しゃくとり法！！！計算量は実装次第だが、 や でできる。

qiita.com

コード

ここでは、「同じ数値が二度登場しない」という条件は、set を用いて判定した。

#include <iostream>
#include <vector>
#include <set>
using namespace std;

int main() {
    /* 入力受け取り */
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    /* しゃくとり法 */
    int res = 0;
    int right = 0;
    set<int> member;

    for (int left = 0; left < n; ++left) {
        while (right < n && !member.count(a[right])) {
            member.insert(a[right]);
            ++right;
        }
        res = max(res, right - left);
        if (left == right) ++right;
        else {
            member.erase(a[left]); // a[left] を削除
        }
    }

    cout << res << endl;
}