【AtCoder】ABC466-D Placing Rooks（Python）

はじめに

AtCoder Beginner Contest 466のD問題「Placing Rooks」の解説記事です。

問題概要

• 問題リンク: ABC466 D - Placing Rooks
• $N \times N$ のマス目がある
• $M$ 回の操作を行う。$i$ 回目の操作では以下を行う：

1. $R_i$ 行目のコマをすべて取り除く
2. $C_i$ 列目のコマをすべて取り除く
3. $(R_i, C_i)$ にコマを置く

• 最終的にマス目に残っているコマの個数を求める

制約:

• $1 \le N, M \le 3 \times 10^5$
• 愚直にシミュレーションすると間に合わないため、工夫が必要です

---

考察：操作を「後ろから」見る

座標を指定すると、その行と列にもともとあった印はすべて消え、指定した座標のみが残ります。

そのため、指定順を後ろから見て、一度出てきた行と列は以降の操作（時系列としては過去の操作）で無視すればよい、ということになります。

後ろから見ていくと、以下のように言い換えることができます。

• すでに処理した（＝未来の操作で上書きされる）行や列の操作は、すべて無視してよい
• まだ一度も登場していない「未出現の行」かつ「未出現の列」への操作だけが、最終的にコマとして残る

つまり、逆順に処理しながら「出現済みの行・列」を記録していけば、1回の操作あたり $O(1)$ で判定可能です。

---

解法・アルゴリズムの流れ

1. 縦軸と横軸で別々に出現済みか調べるリスト ft, fyを作成する。答えとなる数字 ans も初期値ゼロで用意する
2. 入力座標を別のリストにすべて格納してから、ループと pop で逆順に取り出していく
3. 取り出した座標の行と列、両方が未出現であれば、その座標は最後まで残ることになる。そのため答えに +1 する
4. 取り出した座標の行と列を、それぞれ出現済みにする
5. ループ後に答え ans を出力

---

ソースコード (Python)

実際にACしたコードです。

# N（マスのサイズ）と M（操作回数）を入力
n,m=map(int,input().split())
# 縦軸（行）と横軸（列）で別々に出現済みか調べるリストを作成（0で初期化）
ft=[0]*n
fy=[0]*n
# 入力された座標を一時的に保存するリスト
l=[]
for i in range(m):
    # 1-indexedから0-indexed（0始まり）に変換して格納
    a,b=map(int,input().split())
    l.append((a-1,b-1))
# 最終的に残るコマの個数をカウントする変数
ans=0
# ループとpopを使って、座標を後ろ（逆順）から取り出していく
for i in range(m):
    now=l.pop()

    # 取り出した座標の行と列、両方がまだ未出現（0）であれば
    # その座標は未来の操作で消されることなく、最後まで残ることになる
    if ft[now[0]]==0 and fy[now[1]]==0:
        ans+=1
    # 取り出した座標の行と列を、それぞれ出現済み（1）にする
    ft[now[0]]=1
    fy[now[1]]=1
# 最終的な答えを出力
print(ans)

---

計算量

• 時間計算量: $O(N + M)$

• 座標の格納と pop() による逆順ループがそれぞれ $M$ 回、リストの初期化に $O(N)$ かかるため、実行時間制限（2秒）に対して十分に高速

• 空間計算量: $O(N + M)$

• 出現フラグ用リストと、座標格納用リストの分

最後に

どなたかの参考になれば幸いです