AT274の技術だったりなかったり

あっとのTECH LOG

競プロのこととか技術のこととか。たまに日常を書きます。

JOI難易度6 横断幕

問題原文

https://www.ioi-jp.org/camp/2011/2011-sp-tasks/2011-sp-day1.pdf

問題要旨

 H ×  W のグリッドが与えられる。各グリッドの値は 0, 1, 2 のいずれかである。
このグリッドから面積4マス以上の四角形領域を抜き出した時、4つの角にあたるグリッドの値からなる集合が {0, 1, 2} となるようなものの通り数を求めよ。

  •   1 \leq H, W \leq 400

解法

4点固定の全探索は  O((HW)^{4}) となって無理。
1点を決めてその対角線上のもう1点を決めて、残り2点を求めるやり方でも、  O((HW)^{2}) となって無理。

そこで、 「ある縦の選び方2点を固定した時に、その2点とペアになれるような同行の2点はいくつあるのか?」を考えることにする。
まともにやれば計算量は変わらないが、 縦を2点固定した時に、同行にどんな2点の組み合わせがあるのかをカウントした辞書は、  O(H^{2}W) で構築可能。

あとはその辞書を元に求めたいペアの数を計算すればいい。 ちょっとZero-Sum-Rangesっぽい。

実装

集合とかで判定するのも面倒なので、 0, 1, 2 をそれぞれ 10, 1, 100エンコードすることで簡単に判定できるようにしている。
あと defaultdict 使ったらMLEしたので、ありうるキー予めを列挙しておいて普通の辞書でカウントしている。

import sys
my_input = sys.stdin.readline

H, W = map(int, my_input().split())
G = [list(map(int, my_input().split())) for _ in range(H)]

# 0: 10, 1: 1, 2: 100 にエンコード
for h in range(H):
    for w in range(W):
        if G[h][w] == 0:
            G[h][w] = 10
        elif G[h][w] == 2:
            G[h][w] = 100

ans = 0
keys = {2, 11, 20, 101, 110, 200}
for h1 in range(H):
    for h2 in range(h1 + 1, H):
        D = {k: 0 for k in keys}
        for w in range(W):
            D[G[h1][w] + G[h2][w]] += 1

        items = list(D.items())
        for k, v in items:
            if abs(112 - k) in keys:
                ans += v * D[abs(112 - k)]
            if abs(121 - k) in keys:
                ans += v * D[abs(121 - k)]
            if abs(211 - k) in keys:
                ans += v * D[abs(211 - k)]

print(ans // 2)

感想

64MB制限をやめろ。。。 マジでやめろ。。。
すごい綺麗に解けた気がするので個人的には満足です。