きままにものづくり

日々の気付いたことなんかを書いてます。

SRM610Div1Easy

問題

サイズNの二次元配列が与えられる。各要素は1か0である。1と0か繰り返す四角形の最大の面積を求めよ。

解法

(x,y)を考え、そこから1と0を繰り返す幅を探索し、この時の面積を今までの最大の面積と比較し更新する。y+1に移動可能なら同様のことを行い、停止するまで続ける。(x,y)を全探索することで答えが求まる。

計算量

 O(N^4)

コード