TopCoder SRM 837 : Div1 Easy Div2 Hard StairsFromBlocks

Unratedだったけど、Ratedでもレートほとんど動かなさそう。
https://community.topcoder.com/stat?c=problem_statement&pm=17800

問題

1*1のブロックを使い、N段の階段を作ることを考える。
この階段は左から右にブロックN個分の幅を持ち左からx列目にはx個ブロックを積み重ねた形状となっている。

ここで、いくつか1*1より大きなブロックが指定される。
これらのブロックは床に直置きしかできず、互いに重ねることはできない。

これらの大きなブロックをすべて含む最小の階段を作るとき、1*1のブロックは最大何個いるか。

解法

左右逆にして考える。
大きなブロックは当然左から順に置くことになるが、k番目の大きなブロックの右上のブロック位置を考えると、段数Nはmax(H[k]+sum(W[0...k]))以上でなければいけないことがわかる。
この値を小さくしようとすると、大きなブロックはH[i]の大きな順に左に詰めることが良いことがわかる。

class StairsFromBlocks {
	public:
	long long build(vector <int> W, vector <int> H) {
		
		int N=W.size();
		int y,x,i;
		FOR(x,N) {
			FOR(y,N-1) if(H[y]<H[y+1]) {
				swap(W[y],W[y+1]);
				swap(H[y],H[y+1]);
			}
		}
		ll ma=0;
		ll sum=0;
		ll tot=0;
		FOR(i,N) {
			tot+=1LL*W[i]*H[i];
			sum+=W[i];
			ma=max(ma,sum+H[i]-1);
		}
		ll t=ma*(ma+1)/2;
		return t-tot;
		
	}
}

まとめ

問題文の理解に手間取った…。