atcoder練習(2024.11.13)

キーワード

問題

長さ 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≤N≤2×10^5
1≤A_i ≤10^9

入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N
A_1
A_2
…
A_N
出力
B の要素を空白区切りで1行に出力せよ。

入力例 1
5
1 2 1 1 3
出力例 1
-1 -1 1 3 -1
i=1:
A_1 =1 より前に 1 は現れないので、
B_1 =−1 です。
i=2:
A_2 =2 より前に 2 は現れないので、
B_2 =−1 です。
i=3:
A_3 =1 の直前に現れた 1 は A_1 なので、
B_3 =1 です。
i=4:
A_4 =1 の直前に現れた 1 は A_3 なので、
B_4 =3 です。
i=5:
A_5 =3 より前に 3 は現れないので、
B_5 =−1 です。
入力例 2
4
1 1000000000 1000000000 1
出力例 2
-1 -1 2 1

回答

N = int(input())
A = list(map(int, input().split()))

last = {}
B = []

for i in range(N):
  if A[i] in last:
    B.append(last[A[i]] + 1)
  else:
    B.append(-1)
  last[A[i]] = i
    
print(" ".join(map(str, B)))

参考

備考

• 提出形式大事、提出形式が違うだけで結構悩まされていた。
• forをできるだけ減らすかの勝負感がある。アルゴリズムを考えるの大事、いっつも頭の中ではゴリ押しの解法しか思いつかない。もうちょい数学をちゃんと深く勉強していればよかった。
• ゴリ押しの解放しか思いつかないのは手数が少ないからなようか気がする。Pythonの文法をしっかりと理解するのはもちろん、ライブラリ的な発想でまとまった処理についても理解しておくと手数が増えるかも（例えばインプットがそう、なんとなく覚えてきた。）。