kmjp's blog

競技プログラミング参加記です

Saiko~ No Contesuto #01 : ┣¨キ┣¨キ色塗り

終了後に復習参加。
https://www.hackerrank.com/contests/camypapercon01/challenges/painting-bricks

問題

縦横1cm、高さH[i]cmのN個のブロックがあり、水平な地面の上に立っている。
各ブロックの向きは固定である。

これらのブロックを任意の順で手前から奥に(前後の面が接するように)並べていく。
各ブロックのうちある同じ1面を紫、別の同じ1面を黄色で塗ったとき、ブロック群を並べた後連結した図形について、紫の面と黄色の面の面積差の最大値を求めよ。

解法

紫の面を最大化するには、左か右の面を紫にすればよく、その面積はsum(H)cm^2。
黄色の面の最小面積は、以下の何れかである。

  • 上の面を塗ったとき、N(cm^2)となる。
  • ブロックを高い順に並べたとき、手前の面を塗るとmax(H)cm^2

よって解はsum(H)-min(N,max(H))。

int N;
int H[101];
int tot;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>H[i], tot+=H[i];
	sort(H,H+N);
	cout<<max(tot-H[N-1],tot-N)<<endl;
	
}

まとめ

ここらへんはまだ簡単。