【AtCoder】ABC 395 C - Shortest Duplicate Subarray | 緑コーダーが解くAtCoder

atcoder.jp

配点: 300 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 161

問題概要
制約
考察
実装例
コメント

問題概要

長さ $N$ の整数列 $A$ が与えられるので、 $A$ の空でない連続部分列であって、同じ値を複数個含むようなものが存在するか判定せよ。もし存在するならば、そのようなもののうち最も短いものの長さを求めよ。

制約

$1\leq N\leq 2\times 10^5$
$1\leq A_i\leq 10^6$
入力はすべて整数。

考察

条件を満たす $A$ の連続部分列は、左端と右端の数字が必ず同じになる。

もし左右端の文字が異なるならば、「左端を1つ右にずらす」 or 「右端を1つ左にずらす」ことを行って、長さを $1$ 減らすことができるからだ。

さて、ある数字 $A_i$ を右端として定めたとき、左端のインデックスは $A_i = A_j \: (1 \leq j \lt i)$ を満たす $j$ であり、このときの連続部分列の長さは $i - j + 1$ と計算できる。

したがって、各 $i = 1, 2, \cdots, N$ について上述の条件を満たす $j$ を探せばよい。

ただし、この $j$ を探すために毎回forループを使っていては、全体の計算量が $O(N^2)$ となって TLE してしまう。

そこで、直前に $A_i$ が現れたインデックスを記録しておく配列 $\mathrm{pos}$ を用意しておく。

$\mathrm{pos}_i :=$ 直近で数 $i$ が $A$ に現れたインデックス(初期値は $-1$ )

その上で、もし $\mathrm{pos}_{A_i} \neq -1$ であれば、 $j = \mathrm{pos}_{A_i}$ とできる。

このようにして、全体の計算量を $O(N)$ に落とすことができた。

実装例

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

constexpr int INF = 1e+9;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

template <typename T>
inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }

// ======================================== //

int main()
{
    int N;
    cin >> N;
    vector<int> A(N);
    rep(i, 0, N) cin >> A[i];

    vector<int> pos(1000100, -1);
    int ans = INF;
    rep(i, 0, N)
    {
        if (pos[A[i]] != -1)
            chmin(ans, i - pos[A[i]] + 1);

        pos[A[i]] = i;
    }

    if (ans == INF)
        cout << -1 << endl;
    else
        cout << ans << endl;

    return 0;
}