[Atcoder] ABC213(C問題)の整理

概要

• AtCoder Beginner Contest 213 C問題に関して、備忘録を兼ねてコードを整理します。
• 問題は下記のリンクです。

• 環境 : Python 3.8

解法

何の数字も書いていない行・列は取り除かれるため、結果的に$\{A_i\}$, $\{B_i\}$それぞれの要素を、数字が小さい方から順に(最も小さい要素を1として)順位付けすればよいと考えることができます。ただし同じ値の要素は、操作の結果も当然同じ行・列に移動するため同じ順位をつけなければならず、かつ同じ順位が続いた(同じ値の要素が複数あった)場合でも順位は飛ばさない点に注意が必要です。

解答例

# 標準入力
H, W, N = map(int,input().split())
A, B = [], []
for i in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

# 重複を除いた番号と、それが小さい方から何番目かというindexを対応させる辞書を作成
# A:カードがある行数、B:カードがある列数
A_set = set(A)
B_set = set(B)

A_dict, B_dict = {}, {}

for i, A_name in enumerate(sorted(A_set),1):
# enumerateの2番目の引数は、数え始める数値
    A_dict[A_name] = i
    
for j, B_name in enumerate(sorted(B_set),1):
    #B_dict = {B_name:j}
    B_dict[B_name] = j

# 元の配列A,Bにおいて各要素が小さいほう方から数えて何番目かを辞書を参照してprint    
for i in range(N):
    print(A_dict[A[i]], B_dict[B[i]])

公式の解答例を参考に作成しました。特に後半では、$\{A_i\}$, $\{B_i\}$の要素が、それぞれ小さい方から数えて何番目なのか、という順位とセットになった辞書型を作成しています。具体的には($\{A_i\}$に絞って見てみると)、

• $\{A_i\}$から重複を除いた配列を作成。

A_set = set(A)

• sorted関数でA_setを小さい順に並べ替えた上で、enumerate関数で対応した順位とセットにした辞書を作成し、それを1つずつA_dictに保存して辞書を作成。

for i, A_name in enumerate(sorted(A_set),1):
# enumerateの2番目の引数は、数え始める数値
    A_dict[A_name] = i

• 元の配列$\{A_i\}$に関して、作成した辞書を参照しながら、対応する順位を表示。

for i in range(N):
    print(A_dict[A[i]], B_dict[B[i]])

となっています。

コメント

• 問題文を素直に受け取ると「何の数字も書いていない行・列を探索する」ことから始めそうですが、そうすると上手く解けない(または処理時間がオーバーする)と思われます。
• numpyのargsort()関数を用いると、順位付けの際に同じ値の要素を別の順位でつけてしまうため上手くいかないようです。

以上