きままにものづくり

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

SRM636Div1Easy

問題

高さH、幅Wの二次元配列が与えられる。各要素は0~9までの数字を持っている。この配列を縦と横に2つずつ直線を引いて9つのエリアに分割する。エリアの要素の総和がそのエリアの値となる。エリアの値の最小値が最大となる分割方法を見つけ、その時の値を求めよ。

解法

どこに線を引くかを全探索する。このまま、計算をするとO(N^6)となってしまう。
事前に(0,0)から(x, y)までの総和を計算しておくことでO(N^4)に減らすことができる。

計算量

 O(N^4)

コード