ICPC A Garden with Ponds

概要

ICPC 2017 C問題の
「A Garden with Ponds」
を解きました。(python)

問題ページ
judge.u-aizu.ac.jp

回答方針

池となる長方形を、 4重ループで全探索 して、その中で池の容量が最大のものを選ぶ。

回答

1. 池の長方形を 4重ループで全探索 する。
2. 池の中の最大の高さ(max_in_ponds)と、
   周りの壁の最小の高さ(min_wall)を求める。
3. max_in_ponds<min_wallなら 池を作れる ので、体積を計算する。

計算量

• ４重ループ O(n⁴)
• 池のチェックや、体積の計算 O(n²)

まとめると、 O(n⁶)
(制約が小さいからこれで通る)

pythonによる回答

judge.u-aizu.ac.jp