3044

底辺が同一直線上にある矩形が複数あり、それを重ね合わせた図形の上辺の形状が与えられる。このとき、与えられた図形は最小いくつの矩形からなるか答えよ、という問題。

上辺が今までよりも上にある場合には、そこに新規の矩形があると分かる。下にある場合には、取り敢えずそれよりも上にあるものは破棄して、それ以外で一番上にある辺を求める。それと同じ高さならば以前の矩形がそこまで続いていると判断し、そうでなければ新規の矩形があると分かる。