きままにものづくり

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

SRM623Div1Easy

問題

N*Nの平面( N \leq 20)に、ApplePearが置かれている。空白のマスも存在する。ひとつのフルーツを取り出しそれを空のマスへ移動するという操作をK回( K \leq 1000)することができる。Appleで満たされる長方形の最大面積を求めよ。

解法

ある長方形をAppleで満たせるかを全探索する。与えられた平面の中に空白が一つでも存在すればフルーツを動かすことができる。ある長方形をAppleで満たすためのコストは、その中の空白の数eとPearの数pを用いて e + 2pと表せる。
愚直に実装すると、計算量は O(N^6)となる。これでも問題はないが空白、PearAppleの数を事前に計算しておくことで、 O(N^4)となる。

計算量

 O(N^4)
N: 平面のサイズ

コード