2014 TCO Round 2A Easy - SixteenBricks (×)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=13110&rd=15996
・正方形に並べられた１６個のマスがある。
・各マスに、高さheightが分かっているタワーを置く。
・このとき、見えている表面積が最も高くなるようにタワーを置く時の面積を求める。
解き方
・下側は見えないので無視してよさそう。
・上側は常に１６となる。
・あとはどう横に置くか。
→思いつかなかったため、他の人のコードをみてみる。
・サンプルの一つにあるように、互い違いに置くことで（#の場所）８つ分はheight×４を足す。
*#*#
#*#*
*#*#
#*#*
・残りのうち、置く場所によって見えなくなる面の数が異なる。
0#2#
#4#2
2#4#
#2#0
・よってheightでソートし、大きいうちから8つはheight×4を足し、
小さい方から2つはheight×4を引き、次の4つはheight×2を引けばよい。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class SixteenBricks {
public: int maximumSurface(vector<int> height) {
int ret=16;
sort(all(height));
FORE(i,8,16)ret+=height[i]*4;
ret-=(height[0]+height[1])*4;
ret-=(height[2]+height[3]+height[4]+height[5])*2;
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class SixteenBricks {
public: int maximumSurface(vector<int> height) {
int ret=16;
sort(all(height));
FORE(i,8,16)ret+=height[i]*4;
ret-=(height[0]+height[1])*4;
ret-=(height[2]+height[3]+height[4]+height[5])*2;
return ret;
}
};
