問題
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;
}
};
Share this
Related Posts
SRM 491 DIV1 Easy - FoxMakingDice
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11234&rd=14244
解き方
Kを固定することで、そのKを作ることのできる組- SRM 447 DIV1 Easy - KnightsTour
問題
http://community.topcoder.com/stat?c=problem_statement&pm=10577&rd=13901
解き方
問題文の条件をすべて洗い出すのが大事。
洗い出
- SRM 516 DIV1 Easy - NetworkXOneTimePad
問題
http://community.topcoder.com/stat?c=problem_statement&pm=10846&rd=14541
解き方
すべての暗号前の文字と暗号後の文字の組み合わ
- SRM 527 DIV1 Easy - P8XGraphBuilder
問題
http://community.topcoder.com/stat?c=problem_statement&pm=11308&rd=14552
解き方
ｄｐで解く。最終的に２＊ｎ−２個のエッジが発