この記事は 『AtCoder ABC201~225 ARC119~128 灰・茶・緑問題 超詳細解説』 のサンプルです。
【その他のサンプル】
ABC201 A：https://qiita.com/sano192/items/3258c39988187759f756
ABC225 B：https://qiita.com/sano192/items/10133eeb6abc64f1441e
ABC221 D：https://qiita.com/sano192/items/8679200f0f89e636b354
ARC122 B：https://qiita.com/sano192/items/1f314701f2d5b18c8816
「ものすごく丁寧でわかりやすいABC解説」シリーズをベースに【キーワード】【どう考える？】【別解】を追加し、【解説】と【実装のコツ】を分けることでよりわかりやすく、具体例や図もより豊富に全ての問題の解説を書き直しました！
さらにQiitaでは公開していないARC119~128の灰・茶・緑問題も解説しています！
緑を目指す灰・茶コーダーの方へおすすめ！
値段：300円(Kindle Unlimited対象)
【kindle】
【booth(pdf)】
ARC119~128の部分のみ抜粋した廉価版 もあります。
値段：200円(Kindle Unlimited対象)
【kindle】
【booth(pdf)】
【キーワード】
座標圧縮
【どう考える？】
とりあえず紙に図を描いてみる。
行、列は消しても互いに影響しないため、それぞれで考えてよいということがわかるだろう。
空白行を消すということは、カードが置いている行番号が小さい方から何番目なのか、という情報に変換されることを意味する。よってそれぞれのカードの行番号→小さい方から○番目、と変換すればよい。列も同様に考えることで問題を解くことができる。
【解説】
カードの行、列番号がそれぞれ小さい方から何番目なのかへ変換できれば良い。
～例～
H W：5 5
N：5
A1 B1：1 1
A2 B2：4 5
A3 B3：1 2
A4 B4：4 4
A5 B5：5 5
まず図を描く。自分で解く場合にも紙にペンで図を描いてみること。
行を消してみる。
行を消しても①~⑤まで列の番号はまったく変わっていないということがわかる。
各カードについて行番号がどのように変化したか確認すると以下のようになる。
①：1→1
②：4→2
③：1→1
④：4→2
⑤：5→3
行番号はもともと[1,4,5]が存在し、それらが「小さい順から何番目にあるか」という情報に変換されたのがわかる。
1行目→1番目
4行目→2番目
5行目→3番目
ということ。
行番号を受け取り、重複した番号を削除してソートすれば、ある行番号が小さい方から何番目にあるかということは容易に確認できる。
列についても同様の操作を行い、行番号と列番号を変換して出力すればOK。
重複した番号の削除はset、変換先の記録は連想配列を使用する。実装がわからない人は【実装のコツ】からそれぞれ<重複の除去><連想配列>を確認してほしい。
このように「数列の要素」→「小さい順から何番目」と変換する方法を「座標圧縮」と呼ぶ。
【実装のコツ】
＜受け取り＞
入力を受け取る時、単に二次元配列へ[行,列]を格納するだけでは後の処理が面倒。[行,列]を受け取るリストと、行だけ、列だけ受け取るリストを別に用意すれば楽に実装できる。
＜連想配列＞
本問の場合、「行番号」→「小さい順から何番目か」を変換するにはリストを使えば良さそうだがA,Bの最大値が大きすぎてMLE(メモリ制限超過)する。例えばx→yと変換をしたい場合にconvertというリストを作って
convert[x]=y
と記録するならばxとしてありうる最大値分の長さを持つリストを作らねばならない。
A,Bの最大値は10^9で、長さ10^9のリストを作るとメモリが足りなくなる。
そこで「連想配列」を使う。
連想配列は別名「辞書」とも言い、「キー」と対応する「値」を登録できるデータ構造。
pythonには標準で搭載されており、importなども不要。
「使い方」
・連想配列の作成：変数名=dict()
・キー、値の登録、更新【O(1)】：変数名[キー]=値
・値の参照【O(1)】：変数名[キー]
※値が登録されていないキーにアクセスするとエラーとなる
「使用例」
# 連想配列の作成：変数名=dict()
AsArray=dict()
# キー、値の登録、更新【O(1)】：変数名[キー]=値
# キー、値ともに数値、文字列、タプルを入れることが可能
# ただしリストをキーにすることはできない
AsArray[1]=10
AsArray["apple"]="orange"
AsArray[(1,2)]=[3,4,5]
# 値の参照【O(1)】：変数名[キー]
# ※値が登録されていないキーにアクセスするとエラーとなる
print(AsArray[1])
print(AsArray["apple"])
print(AsArray[(1,2)])
連想配列なら最大N個の(キー,値)の組み合わせを作るだけでよく、MLE(メモリ制限超過)しない。
＜for文で2つ以上の要素を取り出す＞
cards=[[A1,B1],[A2,B2],...,[AN,BN]]
となっている場合、以下のように書くことでAi,Biをgyou,retuへ順に格納しながら処理ができる。
for gyou,retu in cards:
意味は以下と同じ。
for i in range(N):
gyou=cards[i][0]
retu=cards[i][1]
便利なので使えるようになろう。
【提出】
# 入力の受け取り
H,W,N=map(int, input().split())
# カードの[行番号,列番号]を受け取るリスト
cards=[]
# 行番号だけ受け取るリスト
gyou=[]
# 列番号だけ受け取るリスト
retu=[]
# N回
for i in range(N):
# 入力の受け取り
A,B=map(int, input().split())
# カードの[行番号,列番号]を受け取り
cards.append([A,B])
# 行番号を受け取り
gyou.append(A)
# 列番号を受け取り
retu.append(B)
# 重複の削除(setにする)
gyou=set(gyou)
# リストに直す(setはソートできない)
gyou=list(gyou)
# ソートする
gyou.sort()
# 変換先を記録する連想配列(conv=convert)
gyou_convert=dict()
# 重複削除後の行の個数分
for i in range(len(gyou)):
# もとの行番号→インデックス番号+1と変換できるように記録(小さい方から何番目にあるか？)
gyou_convert[gyou[i]]=i+1
#列も同じことをする
retu=set(retu)
retu=list(retu)
retu.sort()
retu_convert=dict()
for i in range(len(retu)):
retu_convert[retu[i]]=i+1
# それぞれのカードについて行、列番号を変換して出力
for gyou,retu in cards:
# 行番号の変換
ans_gyou=gyou_convert[gyou]
# 列番号の変換
ans_retu=retu_convert[retu]
# 答えを出力する
print(ans_gyou,ans_retu)