コンテンツにスキップ

DOJ Beginner Contest 8 D - Region of Twos

サイト
DOJ
コンテスト
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 の連続の長さです。