日刊競プロ ABC 235 -C - The Kth Time Query-
問題文
長さ N の数列 A=(a1,a2,…,aN) があります。
以下で説明される Q 個のクエリに答えてください。
クエリ i : 整数の組 (xi,ki) が与えられます。A の要素を a1,a2,… と前から順に見ていったときに、数 x 1,a2,… と前から順に見ていったときに、数 x iが ki回目に登場するのは A の前から何番目の要素を見たときかを出力してください。iが ki回目に登場するのは A の前から何番目の要素を見たときかを出力してください。iが ki回目に登場するのは A の前から何番目の要素を見たときかを出力してください。ただし条件を満たす要素が存在しない場合は −1 を出力してください。
ただし条件を満たす要素が存在しない場合は −1 を出力してください。
制約
1≤N≤2×10**5
1≤Q≤2×10**5
0≤ai≤10**9(1≤i≤N)
0≤xi≤10**9(1≤i≤Q)
1≤ki≤N (1≤i≤Q)
入力はすべて整数である。
考えたこと
xの中でk番目は、元の配列の何番目に出てきますか？
出てこないのであれば、-1を出力してください という問題
熟考した結果、順番を格納する配列が必要だということ。でもって、その配列には何の数字が入っているかわかるようにすれば良い。
（Q[対象の数字]=[何番目に出現するかを格納]みたいな配列をイメージした）
上記の配列が必要だと考えた。。。 ところが良い案が思い浮かばず終了。（aiが最大10**9なのであらかじめ10**9個配列を用意しておくか？等考えていた）
回答を見たところ、考え方は当たっているものの実装できず。。。
連想配列というものを使うとうまく実装できる模様。。。
連想配列とは
ミカン箱に好きな名前を付けられるミカン箱の集まり
と言われても「はぁ？」って感じですね。
真面目に書くと
添字に好きな名前を付けられる配列
です。
添字に好きな名前をつけられる配列らしい。。。（そのまま）
使い方は以下のようにするらしい
ディクショナリ名[キー名] = 値
確かにこれを使えば、キー名をaiの要素、値を出現する順番にすれば実現できそうだ。
解説を見た後の回答
from collections import defaultdict
N,Q = map(int,input().split())
Alist = list(map(int,input().split()))
Qlist = defaultdict(list)
for i in range(N):
Qlist[Alist[i]].append((i+1))
for _ in range(Q):
x,k = map(int,input().split())
if len(Qlist[x])>=k:
print (Qlist[x][k-1])
else:
print (-1)最後のif文については、xの出現回数が求める数ｋ以上であれば、出現順位を答えるようにし、小さければ出現回数が求める数kより小さくなるため、ｋがその回数までは存在しないということで-1を出力している。
これを本番で解ける気がしない。。。