ABC378 C - Repeating

はじめに

11/2開催のABC378のC問題の復習です。

問題文

長さ$N$の正数列$A=(A_1,A_2,…,A_N)$が与えられます。以下で定義される長さ$N$の数列$B=(B_1,B_2,…,B_N)$を求めてください。
$i=1,2,…,N$について、$B_i$を次のように定義する：

• $A_i$と等しい要素が$i$の直前に出現した位置を$B_i$とする。そのような位置が存在しなければ$B_i =−1$とする。より正確には、正整数$j$であって$A_i = A_j$となる$j<i$が存在するならば、そのうち最大の$j$を$B_i$​とする。そのような$j$が存在しなければ$B_i=−1$とする。

自分の提出

考え方としては、
「配列内の要素が前回どこで出現したか」を求める問題なので、
辞書を使って各数値の最後の出現位置を記録します

配列を順番に走査しながら、各要素について、
　1. その数値が前に出現していれば、その位置を配列$B$に記録
　2. 出現したことがないのであれば$-1$を配列$B$に記録

各要素を処理した後、配列$B$を出力する

ABC378_C

def find_previous_num(N, A):
  last_seen = {}
  B = []

  for i in range(N):
    current = A[i]
    if current in last_seen:
      B.append(last_seen[current] + 1) # 0-based indexを出力用に+1
    else:
      B.append(-1)
    last_seen[current] = i

  return B

N = int(input())
A = list(map(int, input().split()))
result = find_previous_num(N, A)
print(*result)

おわりに

Pythonで辞書が使えて楽でした。

ただ、$A_i$の数がもっと多い場合、
if current in last_seen:の部分を少し変えるなど
工夫が必要になったのかもしれません。