AtCoder Beginner Contest 213 C - Reorder Cards【Python】
https://atcoder.jp/contests/abc213/tasks/abc213_c
AtCoder ProblemsのRecommendationで Difficulty: 481、Solve Probability:44%でした。
行と列についてソートし、それぞれ数字を振り直していきましたが同じ列や行にある場合にややこしいことになりました。
解説
https://atcoder.jp/contests/abc213/editorial/2366
を見たところ、今回の問題は座標圧縮と呼ばれるものらしく、セットと辞書を使っており勉強になりました。
H, W, N = map(int, input().split()) cards = [] for i in range(N): a, b = map(int, input().split()) cards.append([a, b, i]) # 行の数字でソート cards = sorted(cards) pre_v = 0 pre_i = 0 for i in range(N): # 前のカードと同じ行にある場合 if pre_v == cards[i][0]: cards[i][0] = pre_i else: pre_v = cards[i][0] cards[i][0] = pre_i + 1 pre_i += 1 # 列の数字でソート cards = sorted(cards, key=lambda x: x[1]) pre_v = 0 pre_i = 0 for i in range(N): # 前のカードと同じ列にある場合 if pre_v == cards[i][1]: cards[i][1] = pre_i else: pre_v = cards[i][1] cards[i][1] = pre_i + 1 pre_i += 1 # 元の順番に戻す cards = sorted(cards, key=lambda x: x[2]) for i in range(N): a, b, i = cards[i] print(a, b)