コンテンツにスキップ

グリッド

タグ「グリッド」の記事 6 件

SamCoding Round 10 (Div. 4) E - Penguins on an Iceberg

n×mn \times m のグリッドがあり、各マスは氷(#)、水(.)、ペンギンが乗った氷(P)のどれかです。グリッドの外はすべて水です。毎晩、水と上下左右に隣り合う氷のマスがすべて同時に溶けて水になります。ペンギンが乗ったマスも普通の氷と同じように溶け、その晩にペンギンは水に落ちます。最後のペンギンが何晩目に水に落ちるかを求める問題です(n,m≤1000n, m \le 1000)。

11 晩目に溶けるのは、水またはグリッドの外と隣り合う氷のマスです。22 晩目に溶けるのは、まだ溶けていない氷のうち、11 晩目に溶けたマスと隣り合うマスです。以下同様に、tt 晩目に溶けるマスは t−1t - 1 晩目に溶けたマスから 11 歩で行けるマスになります。

なので、11 晩目に溶けるマスをすべて始点にした多始点 BFS をすれば、各マスが何晩目に溶けるかが求まります。答えは P のマスの値の最大値です。計算量は O(nm)O(nm) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/utility/range.hpp"
void solve() {
LL(N, M);
VS(S, N);
Rect rect(N, M);
vvl dist(N, vl(M, -1));
deque<pl> que;
for (auto [i, j] : rect) {
if (S[i][j] == '.') {
dist[i][j] = 0;
continue;
}
bool f = false;
for (auto [ni, nj] : rect.neighbors4(i, j)) {
if (S[ni][nj] == '.')
f = true;
}
if (len(rect.neighbors4(i, j)) < 4) {
f = true;
}
if (f) {
que.push_back({i, j});
dist[i][j] = 1;
}
}
while (len(que)) {
auto [i, j] = que.front();
que.pop_front();
for (auto [ni, nj] : rect.neighbors4(i, j)) {
if (dist[ni][nj] == -1) {
dist[ni][nj] = dist[i][j] + 1;
que.push_back({ni, nj});
}
}
}
ll ans = 0;
for (auto [i, j] : rect) {
if (S[i][j] == 'P')
chmax(ans, dist[i][j]);
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

dist[i][j] はマス (i,j)(i, j) が溶ける晩で、水のマスは 00 にしています。Rect は N×MN \times M のマスをまとめて扱う型で、for (auto [i, j] : rect) で全マスを回り、neighbors4(i, j) でグリッド内の上下左右のマスを返します。返ってきたマスが 44 つ未満なら、そのマスはグリッドの端にあり、外の水と隣り合っています。

使用ライブラリ:cpp_include@cb82602

競プロキャンプ2026関西 D - Flowers

H×WH \times W のマス目に、十字形(中心とその上下左右の 5 マス)の「花」が、はみ出さず重ならないようにいくつか描かれています。描かれたマスが # で与えられるので、すべての花の中心を求める問題です(3≤H,W≤10003 \le H, W \le 1000)。

マス目を上の行から順に、各行は左から順に見ていきます。最初に見つかった # は、ある花の一番上のマスです。花の 5 マスのうち、一番上のマスだけがほかの 4 マスより上の行にあり、見る順番が最も早いからです。

そこで、# が見つかったら、その 1 つ下を中心とする花を答えに加え、その花の 5 マスを . に戻します。こうすると、次に見つかる # も、残っている花のどれかの一番上のマスになります。残っている花のマスより前にあるマスは、すべて見終わっていて、そこにあった花は消してあるからです。

最後まで見れば、すべての花の中心が求まります。計算量は O(HW)O(HW) です。

Python
from itertools import product
H, W = map(int, input().split())
S = [list(input()) for i in range(H)]
ans = []
for i, j in product(range(H), range(W)):
if S[i][j] == "#":
ans.append((i + 2, j + 1))
S[i][j] = "."
S[i + 1][j - 1] = "."
S[i + 1][j] = "."
S[i + 1][j + 1] = "."
S[i + 2][j] = "."
print(len(ans))
for x, y in ans:
print(x, y)

product(range(H), range(W)) は、上の行から順に、各行は左から順に (i, j) を並べます。コードの座標は 0 始まりなので、中心 (i+1,j)(i + 1, j) を 1 始まりに直した (i + 2, j + 1) を答えに加えています。花ははみ出さないように描かれているので、S[i + 2][j] などの添字が範囲外になることはありません。

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 を出力します。

DOJ Beginner Contest 6 E - Building a Binary Grid

長さ NN の 01 文字列が QQ 個与えられます。N×NN \times N の 01 のグリッドを 1 つ作り、どの文字列も、グリッド上の長さ NN の経路(上下左右に隣り合う相異なるマスの列)に沿って読めるようにする問題です。グリッドと、各文字列に対応する経路を 1 つずつ出力します。

2≤N≤1002 \le N \le 100 で、NQNQ の総和は 10610^6 以下です。

ii 行目(0-indexed)をすべて i mod 2i \bmod 2 にします。つまり、00 だけの行と 11 だけの行が交互に並びます。さらに、右下の角だけを 11 にします。

0000
1111
0000
1111

(N=4N = 4 の例。NN が偶数なら最下行はもともと 11 です。)

このグリッドでは、角以外のマスについて次のことがいえます。

  • 右か左に動くと、同じ行なので値は変わりません。
  • 上か下に動くと、行が変わるので値が反転します。

左上 (0,0)(0, 0) から始めます。ここは 00 です。次の文字が今のマスと同じ値なら右に、違う値なら下に動きます。

右か下にしか動かないので、同じマスを 2 回通ることはありません。N−1N - 1 回動いたあとも、行と列の番号の和は N−1N - 1 なので、グリッドからはみ出しません。また、右下の角(番号の和が 2N−2>N−12N - 2 > N - 1)には届かないので、角だけ値を変えたことの影響も受けません。

右下の角 (N−1,N−1)(N - 1, N - 1) から始めます。ここは 11 です。次の文字に合わせて、左か上に動きます。

角から左のマスと上のマスは、行が違うので値が異なり、どちらかは次の文字と一致します。そこから先は、0 で始まる場合と同じように「同じ値なら左、違う値なら上」と動けば、どの文字列も読めます。左か上にしか動かないので、角に戻ることもありません。

1 つの文字列の経路は O(N)O(N) で求まるので、全体で O(NQ)O(NQ) です。

Python
for _ in range(int(input())):
N, Q = map(int, input().split())
grid = []
for i in range(N):
grid.append([i % 2] * N)
grid[-1][-1] = 1
for i in range(N):
print(*grid[i], sep="")
for _ in range(Q):
S = input()
if S[0] == "0":
i, j = 0, 0
ans = [i + 1, j + 1]
for k in range(1, N):
if grid[i][j + 1] == int(S[k]):
j += 1
ans.append(i + 1)
ans.append(j + 1)
else:
i += 1
ans.append(i + 1)
ans.append(j + 1)
else:
i, j = N - 1, N - 1
ans = [i + 1, j + 1]
for k in range(1, N):
if grid[i][j - 1] == int(S[k]):
j -= 1
ans.append(i + 1)
ans.append(j + 1)
else:
i -= 1
ans.append(i + 1)
ans.append(j + 1)
print(*ans)

隣のマス(右または左)の値が次の文字と一致すれば横に、一致しなければ縦に動いています。縦に動いた先は、横のマスと値が逆なので、必ず次の文字と一致します。

DOJ Beginner Contest 8 D - Region of Twos

00 と 11 からなる長さ NN の数列 AA と、長さ MM の数列 BB が与えられます。NN 行 MM 列の配列 CC を Ci,j=Ai+BjC_{i,j} = A_i + B_j で定めます。値が 22 のマスだけを考え、辺を共有するマスどうしをつないだときの連結成分のうち、最大のものの面積を求める問題です。値が 22 のマスがなければ 00 を出力します。

N,M≤2×105N, M \le 2 \times 10^5 なので、CC を実際に作ることはできません。

Ci,j=2C_{i,j} = 2 となるのは、Ai=1A_i = 1 かつ Bj=1B_j = 1 のときだけです。

AA で 11 が連続している区間を行の区間、BB で 11 が連続している区間を列の区間として、その組み合わせごとに長方形ができます。

  • 長方形の中のマスはすべて値が 22 で、つながっています。
  • 隣の長方形との間には、Ai=0A_i = 0 の行か Bj=0B_j = 0 の列があるので、別の長方形とはつながりません。

したがって、連結成分はこの長方形そのものです。最大の面積は、AA で 11 が連続する最大の長さと、BB で 11 が連続する最大の長さの積になります。値が 22 のマスがない場合も、どちらかが 00 になるので、積は 00 で正しく求まります。

Python
for _ in range(int(input())):
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
x = 0
t = 0
for a in A:
if a:
t += 1
else:
t = 0
x = max(x, t)
y = 0
t = 0
for a in B:
if a:
t += 1
else:
t = 0
y = max(y, t)
print(x * y)

x が AA の、y が BB の、11 が連続する最大の長さです。t は今見ている位置で終わる 11 の連続の長さです。

DOJ Beginner Contest 9 D - Harvesting the Farm

RR 行 CC 列の農場の NN 個のマスに作物があり、ii 番目の作物は YiY_i 行 XiX_i 列にあります。

収穫機は 1 つの列の中で、連続するいくつかの行を占めます。最初は SrS_r 行 ScS_c 列の 1 マスだけを占めています。収穫機には次の 2 つの操作ができます。

  • 拡張:収穫機の上端か下端に 1 マス付け足す。
  • 移動:収穫機全体を左か右に 1 マスずらす。

操作のあと収穫機が占めるマスに作物があれば、すぐに収穫されます。収穫機が農場の外にはみ出してはいけません。すべての作物を収穫するのに必要な操作回数の最小値を求める問題です。

テストケースは T≤5×104T \le 5 \times 10^4 個あり、NN の総和は 10510^5 以下です。

作物と収穫機の最初の位置を合わせて、

  • 行の最小値を uu、最大値を dd
  • 列の最小値を ll、最大値を rr

とします。答えは

(d−u)+(r−l)+min⁡(Sc−l,r−Sc)(d - u) + (r - l) + \min(S_c - l, r - S_c)

です。

拡張は d−ud - u 回必要で、それで足りる

Section titled “拡張は d−ud - ud−u 回必要で、それで足りる”

収穫機は常に SrS_r 行を含み、拡張 1 回で 1 行ずつしか広がりません。uu 行と dd 行の作物を収穫するには、収穫機がどこかで uu 行と dd 行に届く必要があります。収穫機は縮まないので、最終的には uu 行から dd 行まで全部を占めることになり、拡張は少なくとも d−ud - u 回必要です。

逆に、最初に ScS_c 列で uu 行から dd 行まで広げてしまえば、あとはどの列に行っても、その列の作物はすべて収穫できます。

移動は (r−l)+min⁡(Sc−l,r−Sc)(r - l) + \min(S_c - l, r - S_c) 回必要で、それで足りる

Section titled “移動は (r−l)+min⁡(Sc−l,r−Sc)(r - l) + \min(S_c - l, r - S_c)(r−l)+min(Sc​−l,r−Sc​) 回必要で、それで足りる”

ll 列から rr 列までのすべての列に、収穫機が少なくとも 1 回は行く必要があります。ScS_c 列から始めて両端に行く最短の動き方は、近いほうの端に行ってから、反対の端まで行くことです。

  • 先に左端に行くと、(Sc−l)+(r−l)(S_c - l) + (r - l) 回
  • 先に右端に行くと、(r−Sc)+(r−l)(r - S_c) + (r - l) 回

なので、移動は (r−l)+min⁡(Sc−l,r−Sc)(r - l) + \min(S_c - l, r - S_c) 回です。

拡張を先に全部済ませてから移動すれば、両方の下限を同時に達成できます。

Python
for _ in range(int(input())):
R, C = map(int, input().split())
Sr, Sc = map(int, input().split())
N = int(input())
YX = [tuple(map(int, input().split())) for i in range(N)]
u = d = Sr
l = r = Sc
for y, x in YX:
u = min(u, y)
d = max(d, y)
l = min(l, x)
r = max(r, x)
ans = d - u
f = min(Sc - l + r - l, r - Sc + r - l)
print(ans + f)

ans が拡張の回数、f が移動の回数です。