TopCoderOpen 2014 Round2A Easy SixteenBricks

Mediumが解けなかったけど、SRM620でレート落とした後なのでちょっとレート回復。
http://community.topcoder.com/stat?c=problem_statement&pm=13174

問題

縦1、横1、高さheight[i]の直方体が16個与えられる。
この直方体16を4x4の形に並べたい。

この図形の表面積を最大化せよ。

解法

高さの高い直方体を隣接させると、互いの面を隠しあって表面積が大きく減少してしまう。
よって、まず上位8つを以下のように市松模様に配置する。

#.#.
.#.#
#.#.
.#.#

この８つは互いに隣接せず干渉しないので、４面分height[i]*4の表面積を得られる。
残り８つを置くわけだが、以下のように場所に応じて他の直方体の面を覆う数が異なる。

#3#2
3#4#
#4#3
3#3#

表面積を最大化したいので、他の面と多く干渉する位置から順に高さの低い直方体を置いていけばよい。

class SixteenBricks {
	public:
	int maximumSurface(vector <int> height) {
		int H=16,i,ret=0;
		sort(height.begin(),height.end());
		
		ret=16;
		for(i=8;i<H;i++) ret+=height[i]*4;
		ret-=(height[0]+height[1])*4;
		ret-=(height[2]+height[3]+height[4]+height[5])*2;
		return ret;
		
		
	}
}

まとめ

bitdpと見せかけて実は割とあっさりな問題。
これが思いつくまで時間がかかったけど、面白い問題だった。