JOI難易度6 横断幕
問題原文
https://www.ioi-jp.org/camp/2011/2011-sp-tasks/2011-sp-day1.pdf
問題要旨
× のグリッドが与えられる。各グリッドの値は 0
, 1
, 2
のいずれかである。
このグリッドから面積4マス以上の四角形領域を抜き出した時、4つの角にあたるグリッドの値からなる集合が {0, 1, 2}
となるようなものの通り数を求めよ。
解法
4点固定の全探索は となって無理。
1点を決めてその対角線上のもう1点を決めて、残り2点を求めるやり方でも、 となって無理。
そこで、 「ある縦の選び方2点を固定した時に、その2点とペアになれるような同行の2点はいくつあるのか?」を考えることにする。
まともにやれば計算量は変わらないが、 縦を2点固定した時に、同行にどんな2点の組み合わせがあるのかをカウントした辞書は、 で構築可能。
あとはその辞書を元に求めたいペアの数を計算すればいい。 ちょっと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制限をやめろ。。。 マジでやめろ。。。
すごい綺麗に解けた気がするので個人的には満足です。