概要

\(N\) 個の花壇の座標が与えられ、それぞれの花壇を1つずつ取り除いたときの配置図における空きセル数を求めよ。

考察

この問題では、各花壇を取り除いた後の「配置図」を作る必要があります。配置図は、登場する \(X\) 座標と \(Y\) 座標の種類数によって決まるグリッドサイズ \(C_x \times C_y\) に基づいています。

素朴な方法として、毎回 \(N-1\) 個の点について、\(X\), \(Y\) の種類数を集計してグリッドサイズを計算する方法がありますが、これは各点について \(O(N)\) かかるため、全体で \(O(N^2)\) となり、制約 \(N \leq 2 \times 10^5\) では間に合いません。

そこで、事前にすべての点に対する \(X\), \(Y\) 座標の出現回数をカウントしておけば、ある点を取り除いたときにその \(X\), \(Y\) 座標が消失するかどうか（つまりグリッドのサイズが縮小するかどうか）を \(O(1)\) で判定できます。具体的には、その座標がただ1つの点にしか含まれていなければ、取り除いたときにその座標の種類数が1減ることになります。

このように前処理を行うことで、全体の計算量を \(O(N \log N)\) に抑えることができます（ソートがボトルネック）。

アルゴリズム

1. 全点の \(X\), \(Y\) 座標を収集し、それぞれ重複を除いてソートして一意なリストを得る。
2. 各座標値をそのリストにおけるインデックスに変換し、インデックスごとの出現回数を記録する。
3. 全体でのグリッドサイズ \(C_x \times C_y\) を計算し、空きセル数 \(C_x \cdot C_y - N\) を求める。
4. 各点について以下を行う：
   • その点の \(X\), \(Y\) インデックスに対応する出現回数を見て、1であればその軸方向のサイズが1減少すると判断。
   • 新しいグリッドサイズから新しい空きセル数を計算し、出力する。

計算量

• 時間計算量: \(O(N \log N)\)（主に座標のソート）
• 空間計算量: \(O(N)\)

実装のポイント

• 座標圧縮を行うことで、無駄な大きな座標値を扱わず、インデックスベースで管理できる。

• 出現回数を defaultdict で管理することで、各点の影響を高速に取得できる。

• 各点の除去による影響は、「その点しかない座標があるかどうか」だけなので、そこだけチェックすればOK。

  ソースコード

import sys
from collections import defaultdict

input = sys.stdin.read
data = input().split()

N = int(data[0])
XY = [(int(data[2*i+1]), int(data[2*i+2])) for i in range(N)]

Xs = [x for x, y in XY]
Ys = [y for x, y in XY]

sorted_X = sorted(set(Xs))
sorted_Y = sorted(set(Ys))

X_to_idx = {x: i for i, x in enumerate(sorted_X)}
Y_to_idx = {y: i for i, y in enumerate(sorted_Y)}

# 各x, yの出現回数
count_x = defaultdict(int)
count_y = defaultdict(int)

for x, y in XY:
    count_x[X_to_idx[x]] += 1
    count_y[Y_to_idx[y]] += 1

Cx = len(sorted_X)
Cy = len(sorted_Y)

total_cells = Cx * Cy
empty_cells_all = total_cells - N

results = []

for x, y in XY:
    idx_x = X_to_idx[x]
    idx_y = Y_to_idx[y]
    
    # x座標の種類数の変化
    if count_x[idx_x] == 1:
        new_Cx = Cx - 1
    else:
        new_Cx = Cx
        
    # y座標の種類数の変化
    if count_y[idx_y] == 1:
        new_Cy = Cy - 1
    else:
        new_Cy = Cy
    
    new_total_cells = new_Cx * new_Cy
    new_empty_cells = new_total_cells - (N - 1)
    results.append(new_empty_cells)

print('\n'.join(map(str, results)))

この解説は qwen3-coder-480b によって生成されました。