abc186f

NISHIO Hirokazu [Translate]

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

    ret = 0
    # horizontal -> vertical
    for x in range(0, minX[0]):
        ret += minY[x]

    # grouping
    from collections import defaultdict
    P2 = defaultdict(list)
    for i in range(M):
        x, y = PS[i]
        P2[y - 1].append(x - 1)

    bit_init(H + 1)
    x0 = minX[0]
    for y in range(0, minY[0]):
        x1 = minX[y]
        if x1 > x0:
            ret += x1 - x0
            x1 = x0
        ret += bit_sum(x1)
        for x in P2[y]:
            bit_set(x, 1)

    return ret