ABC186F
from ABC186
ABC186F
https://gyazo.com/ecac49bfec2162e0a6e196eff9d3cd89
F - Rook on Grid
かきかけ
考えたこと
タテヨコでたどり着く方法とヨコタテでたどり着く方法がある
個別に数えて足すと2通りの方法でたどり着けるところがダブルカウントになる
ダブルカウントのものの効率良い数え方を考える
余事象を引く方が楽ではないか？
つまり「たどり着けないマスを数えて全体から引く
https://gyazo.com/0bfc6272ea8fb38766722b788bda44bb
この交点が「たどりつけないマス」
各xにおける最小のyをminY[x]とする
欲しいのはminY[x] < yの範囲にあるminX[y] <= xの数
こういうパターン、見たことがあるぞ…
Scrapboxから関連しそうなものを探す
削除可能集合で不等号条件
ACL1A
今回の目的と完全には一致しないが以下の要素は使えそう
フェニック木を使う
値域は0/1で、値の存在不在を表現
まとめた 長方形区間カウント
素朴にminY[x] < yの範囲にあるminX[y] <= xの数を数えるコードを書き、同じ結果になるようにフェニック木を使うバージョンを実装
提出→WA
素朴実装とフェニック木実装の食い違いをランダムテストで調べているうちに、素朴実装が間違っていることに気づいた
こういうパターン
https://gyazo.com/3fc29bf88b7be3fcc5ccbe6a7b25690e
公式解説
フェニック木を使う方針はOK
たどり着けないところを数えるのではなく2通りでたどり着けるところを数えている
AC
code:python
def solve(H, W, M, PS):
minX = H * W
minY = W * H
for x, y in PS:
minXy - 1 = min(minXy - 1, x - 1)
minYx - 1 = min(minYx - 1, y - 1)
ret = 0
# horizontal -> vertical
for x in range(0, minX0):
ret += minYx
# grouping
from collections import defaultdict
P2 = defaultdict(list)
for i in range(M):
x, y = PSi
P2y - 1.append(x - 1)
bit_init(H + 1)
x0 = minX0
for y in range(0, minY0):
x1 = minXy
if x1 > x0:
ret += x1 - x0
x1 = x0
ret += bit_sum(x1)
for x in P2y:
bit_set(x, 1)
return ret