AtCoder Beginner Contest Edit

【pythonでABC213を解説】C - Reorder Cards

問題概要

問題ページ

問題文

\(H\) 行 \(W\) 列の格子状に \(HW\) 枚のカードが並べられています。
\(i=1,\ldots,N\) について、上から \(A_i\) 行目、左から \(B_i\) 列目にあるカードには数 \(i\) が書かれており、それ以外の \(HW-N\) 枚のカードには何も書かれていません。

これらのカードに対し、以下の \(2\) 種類の操作を可能な限り繰り返します。

  • 数の書かれたカードを含まない行が存在するとき、その行のカードを全て取り除き、残りのカードを上へ詰める
  • 数の書かれたカードを含まない列が存在するとき、その列のカードを全て取り除き、残りのカードを左へ詰める

操作が終了したとき、数が書かれたカードがそれぞれどこにあるか求めてください。なお、答えは操作の仕方に依らず一意に定まることが証明されます。

制約

  • \(1 \leq H,W \leq 10^9\)
  • \(1 \leq N \leq \min(10^5,HW)\)
  • \(1 \leq A_i \leq H\)
  • \(1 \leq B_i \leq W\)
  • \((A_i,B_i)\) は相異なる
  • 入力に含まれる値は全て整数である

問題の考察

ACコード

import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    h, w, n = list(map(int, input().rstrip('\n').split()))
    ad = collections.defaultdict(int)
    bd = collections.defaultdict(int)
    ab = []
    for i in range(n):
        a, b = list(map(int, input().rstrip('\n').split()))
        ab.append([a, b])
        ad[a], bd[b]
    al = 0
    ac = 0
    for k in sorted(ad.keys()):
        ac += k - al - 1
        al = k
        ad[k] = ac
    bl = 0
    bc = 0
    for k in sorted(bd.keys()):
        bc += k - bl - 1
        bl = k
        bd[k] = bc
    for a, b in ab:
        print(a - ad[a], b - bd[b])


if __name__ == '__main__':
    solve()

プログラミング

-AtCoder Beginner Contest, Edit
-