今更考えるABC過去問 ~ABC395 C問題~

問題

解答案

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

int main() {
    int N;
    cin >> N;

    vector<int> B(1000009, -1);
    int A;
    int ans = N + 1;
    
    for (int i=1; i<=N; i++) {
        cin >> A;
        if (B[A] != -1) {
            ans = min(ans, i - B[A] + 1);
        }
        B[A] = i;
    }

    if (ans == N + 1) cout << -1 << endl;
    else cout << ans << endl;
}

ある値が出現した位置を配列に記憶し、再び現れたときに位置の差分を取ることで距離が求められる。その最小値が答えとなる。記憶する位置は直前のものだけで良い。