コンテンツにスキップ

DOJ Beginner Contest 12 C - Nature-Friendly Village

サイト
DOJ
コンテスト
DOJ Beginner Contest 12
問題
C - Nature-Friendly Village

R×CR \times C のグリッドの各マスは、家(#)か空き地(.)です。空き地に 1 本ずつ木を植えます。家ごとに周囲 8 マスに植えた木の本数を数え、その総和を KK 以上にしたいです。植える木の本数の最小値を求める問題です。できなければ −1-1 を出力します(0≤K≤8RC0 \le K \le 8RC、全テストケースの RCRC の総和は 10610^6 以下)。

総和を、木の側から数え直します。空き地 xx の周囲 8 マスにある家の個数を cxc_x とすると、xx に植えた木は、総和をちょうど cxc_x だけ増やします。したがって総和は、木を植えた空き地の cxc_x の和です。

この和を KK 以上にするには、cxc_x の大きい空き地から順に植えていくのが最善です。何本植えるにしても、同じ本数なら cxc_x の大きいほうから選んだときに和が最大になるからです。すべての空き地に植えても KK に届かなければ、答えは −1-1 です。

計算量はソートがいちばん重く、O(RClog⁡(RC))O(RC \log(RC)) です。

Python
from itertools import product
for _ in range(int(input())):
R, C, K = map(int, input().split())
S = [input() for i in range(R)]
l = []
for i, j in product(range(R), range(C)):
if S[i][j] == "#":
continue
c = 0
for di, dj in product(range(-1, 2), repeat=2):
if di == dj == 0:
continue
ni, nj = i + di, j + dj
if ni not in range(R):
continue
if nj not in range(C):
continue
if S[ni][nj] == "#":
c += 1
l.append(c)
l.sort()
s = 0
ans = 0
while l and s < K:
s += l.pop()
ans += 1
if s < K:
print(-1)
else:
print(ans)

l は空き地ごとの cxc_x の列です。昇順にソートして末尾から pop することで、大きいほうから取り出しています。s が KK に届くか、空き地がなくなるまで植えます。K=0K = 0 のときは 1 本も植えずに 00 を出力します。