ABC213 C - Reorder Cards

atcoder.jp

行と列を取り除く２種類の操作を行うと，数字の書いていない行と列はすべて消える．
与えられたAとBをそれぞれ昇順にソートし，出現した順番で新たに添え字を割り振り，変換表を作る．つまりA=[1, 10, 100, 1000] であれば，newA=[1,2,3,4]という風に変換を行う．下のコードでは辞書r_H，r_Wで変換表を作っている．（これは座標圧縮と呼ばれるらしい．後で調べよ．） 最後にその変換表を使って，Ai，Biの変換を行い，答えを出力する．

H, W, N = list(map(int, input().split()))
AB = [list(map(int, input().split())) for i in range(N)]

A=[]
B=[]
for ab in AB:
    A.append(ab[0])
    B.append(ab[1])

A.sort()
B.sort()

r_H = dict()
r_W = dict()

ind_H = ind_W = 1
prev_a = prev_b = -1
for a,b in zip(A,B):
    if prev_a != a:
        r_H[a] = ind_H
        ind_H += 1
        prev_a = a
    
    if prev_b != b:
        r_W[b] = ind_W
        ind_W += 1
        prev_b = b
    

for ab in AB:
    print(r_H[ab[0]], r_W[ab[1]])

所要時間

45分(Median Solve Time:36mins)