ABC406のD問題Garbage Removalの復習
AtCoder Beginner Contest 406 (ABC406)の D 問題 Garbage Removal をコンテスト後に正解できたメモ。ゴミの位置は (X, Y)で与えられるが、二次元配列ではなく各 row と column 毎にSet型で保持するのがポイント。
問題 D - Garbage Removal
- 二次元の配列があり、そのマップ上にゴミが配置される。
- 与えられた Query に対応する row または column 上にあるゴミの数を報告する。
- ゴミの数を報告したら、報告したゴミはマップ上から削除する。
sample データから、同じ場所のゴミの数を再度問い合わされる場合があることが分かる。
方法
コンテスト内では単純な二次元配列にゴミの位置をマップして、Query 毎に数えたが制限時間オーバー (TLE)となり正解できませんでした。
そこで正解 (AC)となった回答を見て復習しました。
各 row と column 毎に保存
ゴミの位置を 2 次元の配列として管理していては、計算速度が全然足りません。これを回避する鍵は、ゴミの位置を一元的に管理するのではなく、row と column に分けて管理することです。
row と column に分けることで、全幅をスキャンする必要なく直接 Query で指定された row または column にあるゴミのデータにアクセスできます。
ゴミの消去は全幅スキャンしない
Query と反対側の軸 (row または column) のデータを削除する時に、全ての項を見ていては時間の無駄です。そこで Query で報告したデータを活用します。
この値には、反対側の軸のどこにゴミがあるかが入っています。そこで、ゴミのある場所だけをピンポイントで選んでボミの記録を消すことで TLE を回避します。
技術的工夫
同じ Query が複数回あるので、Query を記録しておくようにしました。そして再度の Query だった場合には、その row または column のゴミは消去済みなのでゴミを確認しないで0を返すようにしました。同時にゴミの数を調べないので、その row または column のデータは削除しないで計算時間の短縮を期待しました。しかし時間短縮効果はほとんどありませんでした。
Set型のremoveとdiscardメソッドの違い
Set型から項目を削除するには、removeとdiscardがあります。どちらも同じくSetから項を削除しますが、存在しない項を削除しようとした時に差異があります。
removeは、存在しない項を削除しようとすると例外が引き起こされます。対してdiscardは、項が存在しなくても例外は起きません。
そこで、項が存在しないことを知る必要がない場合は、discardを使ったほうが例外処理をする必要がなく簡単です。
計算時間の短縮も可能
私のコードでは最長の実行時間が 1000ms 程度かかっていますが、他の方の結果を見ると Python のコードであってもゴミの管理にDicit型を使うことで、計算時間をこの半分程度まで速くすることができるようです。
h, w, n = map(int, input().split())
garbage_row = [set() for _ in range(h)]
garbage_column = [set() for _ in range(w)]
for _ in range(n):
x, y = map(int, input().split())
# fit for array
x -= 1
y -= 1
garbage_row[x].add(y)
garbage_column[y].add(x)
q = int(input())
Query = set()
for _ in range(q):
c, xy = map(int, input().split())
xy -= 1 # fit for array
if (c, xy) in Query:
# skip the same Query
print(0)
elif c == 1:
garbage = garbage_row[xy]
print(len(garbage))
# clean garbage
# garbage_row[xy] = set() # no need to clear by remembering queries
# avoid scan all
for i in garbage:
garbage_column[i].discard(xy)
else:
garbage = garbage_column[xy]
print(len(garbage))
# clean garbage
# garbage_column[xy] = set() # no need to clear by remembering queries
# avoid scan all
for i in garbage:
garbage_row[i].discard(xy)
Query.add((c, xy))