実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 191

問題概要

長さ $N$ の正整数列 $A$ が与えられるので、以下で定義される長さ $N$ の数列 $B$ を求めよ。

$i=1,2,\cdots,N$ について、 $A_i$ と等しい要素が $i$ の直前に出現した位置を $B_i$ とする。そのような位置が存在しなければ $B_i=-1$ とする。

制約

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

考察

定義通り $i$ を $1$ から順に増やしていき、 $B_i$ の値を確定させていけばよい。

工夫すべきなのはデータの持ち方、すなわち $A_i = A_j \: (j \lt i)$ を満たす最大の $j$ の記憶方法である。 $1 \leq A_i \leq 10^9$ なので、普通にvectorを使うと MLE となってしまう。

そこで、keyをある値 $x$ 、 valueを「 $A_j = x$ となる $j \: (1 \leq j \lt i)$ の中で最大のもの」とするような連想配列 (ここではlast_posとした) を用意する。その上で、以下のようなアルゴリズムにより解くことができる。

$A_i$ を先頭から見ていく。
現時点でlast_posにkey が含まれているとき
1. $B_i = \mathrm{last\_pos}_{A_i}$ とする。
そうでないとき
1. $\mathrm{last\_pos}_{A_i} = i + 1$ とする。

コード

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

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

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

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

    vector<int> B(N, -1);
    unordered_map<int, int> last_pos;
    rep(i, 0, N)
    {
        if (last_pos.contains(A[i]))
            B[i] = last_pos[A[i]];

        last_pos[A[i]] = i + 1;
    }

    rep(i, 0, N) cout << B[i] << " ";
    cout << endl;

    return 0;
}