ABC113-C問題をPythonでとく

ABC113-C問題

問題はこれ
考える手順としては、

  1. 入力される県ごとに誕生年を昇順ソート
  2. その順番を記憶し、入力された順番で県の番号(6桁) + 誕生年(6桁)を出力

という感じでやっていく。詰まったのは入力順をどうやって記録しておくかだった。書かれるとわかるが脳内で考えてるおぼろげな状態だとうまく解決するのに時間がかかった。
以下コード(提出はこれ)

# coding: utf-8  
N, M = map(int, input().split())  
# 入力を県ごとにまとめる  
p_dict = {}  
for i in range(M):  
    p, y = map(int, input().split())  
    # p_dictには[year, preference, input_index]を入れる  
    if p not in p_dict.keys():  
        p_dict[p] = [[y, p, i]]  
    else:  
        p_dict[p].append([y, p, i])  
ans = []  
for p in p_dict.keys():  
        # 県で昇順ソート  
    p_dict[p].sort()  
    for i in range(len(p_dict[p])):  
        # 昇順で並べたときの順番を入れとく  
        p_dict[p][i].append(i+1)  
        # 辞書型はソートできないのでリストに入れとく  
        ans.append(p_dict[p][i])  
# ans = [y, p, input_index, sorted_index]  
# 入力順(input_index)でソート  
ans.sort(key=lambda x: x[2])  
for y, p, oi, si in ans:  
    print("{:06d}{:06d}".format(p, si))  

めちゃくちゃ時間かかった。今回は考察は全然要らなかったけど実装力がダメすぎた。どっちも精進していきたい。