T2M_MJM

大学などで学んだことを真面目に書いていきます。

AtCoder Beginner Contest 045 D 問題

勉強を兼ねて AtCoder Beginner Contest 045 の D 問題を解いたので、解くまでの経過も兼ねてメモ代わりに記事にしておきます。

abc045.contest.atcoder.jp

問題概要

白黒で塗りつぶされたマス目を、 3 * 3 の9マス領域を一纏まりとして走査していき、9マス中何マスが黒になっているのかを数え上げる問題です。

問題解答

盤面全体のサイズは 1018 にまでなってしまうので、盤面のデータを全て保持していてはメモリ制限を簡単にオーバーしてしまいます。 対して、実際に塗りつぶされるマスの数は最大でも 105 なので、こっちを上手に使ってあげれば良さそうです。

今回は、あるマスが塗りつぶされる度に、そのマスを含む 9 マス領域の情報を更新していくようにしてあげました。1つのマスは最大で 9 つの 9マス領域に属しますが、オーダーは 105 のままなので、メモリ制限も問題無さそうです。

from itertools import product

H, W, N = 0, 0, 0
filled = {}

def boundary_check(pos):
    """
    (x, y) -> bool
    """
    return pos[0] < W - 2 and pos[1] < H - 2 and pos[0] >= 0 and pos[1] >= 0

def matrix_cell_in(a, b):
    """
    int -> int -> (int, int)

    塗りつぶされたセルの座標から、そのセルが含まれる 3 * 3 連続セルの集合を返す。
    3 * 3 連続セルは左上セルの座標で表現する。
    """
    matrixes = list(product(range(a-2,a+1),(range(b-2, b+1))))
    return list(filter(boundary_check ,matrixes))
    # return matrixes

def fill(pos, cell):
    """
    (int, int) -> unit

    3 * 3連続セルの座標を受け取って、その中の黒マスの数を増やす。
    まだ塗られていなかった場合は 1 にする。
    """
    if pos in filled:
        filled[pos] += 1
    else:
        filled[pos] = 1


H, W, N = map(int, input().split(" "))

for i in range(N):
    b, a = map(int, input().split(" "))
    a, b = a-1, b-1
    for cell in matrix_cell_in(a,b):
        fill(cell, (a,b))

results = [0 for _ in range(10)]
for v in filled.values():
    results[v] += 1

results[0] =  (H - 2) * (W - 2)  - sum(results)

for r in results:
    print(r)

問題を解くための諸々

今回の問題は恐らくメモリ制限をクリアすることが主だったのかなと思います。配列ではなくハッシュを使うことで全体の容量を節約できれば、後は問題なく解けたのではないでしょうか。