DOJ Beginner Contest 8 D - Region of Twos
- サイト
- DOJ
- コンテスト
- DOJ Beginner Contest 8
- 問題
- D - Region of Twos
と からなる長さ の数列 と、長さ の数列 が与えられます。 行 列の配列 を で定めます。値が のマスだけを考え、辺を共有するマスどうしをつないだときの連結成分のうち、最大のものの面積を求める問題です。値が のマスがなければ を出力します。
なので、 を実際に作ることはできません。
となるのは、 かつ のときだけです。
で が連続している区間を行の区間、 で が連続している区間を列の区間として、その組み合わせごとに長方形ができます。
- 長方形の中のマスはすべて値が で、つながっています。
- 隣の長方形との間には、 の行か の列があるので、別の長方形とはつながりません。
したがって、連結成分はこの長方形そのものです。最大の面積は、 で が連続する最大の長さと、 で が連続する最大の長さの積になります。値が のマスがない場合も、どちらかが になるので、積は で正しく求まります。
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 が の、y が の、 が連続する最大の長さです。t は今見ている位置で終わる の連続の長さです。