けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

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

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

問題概要

長さ  N の正の整数列  A_{1}, \dots, A_{N} が与えられる。

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

制約

  •  1 \le N \le 10^{5}
  •  1 \le A_{i} \le 10^{5}

考えたこと

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


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


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

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;
}