CODE FESTIVAL 2015 あさプロ Hard : B - 立方体とペンキ

これは何とか解けた。
http://code-festival-2015-morning-hard.contest.atcoder.jp/tasks/cf_2015_morning_hard_b

問題

1辺1の立方体がある。
これらを地面の上に横1列に隙間なくN個並べた。
また、それぞれその上にさらに立方体を積み重ね、端からi個目の列には計A[i]個の立方体が積まれた状態となった。

この立方体群に対し、地面または他の立方体に面していない面をペンキで塗ることを考える。
最大K個立方体を取り除ける時、ペンキを塗れる面積を最小化せよ。
ただし、どの列も最低1個は立方体を残すこと。

解法

立方体の除去に寄らず、上面の総面積はNである。
また、前面及び背面はどの立方体を選んでも面積の減少量は同じであり、その結果それぞれの面積はsum(A)-Kである。

となると、ペンキを塗る面積を減らすには、左及び右の面を減らすしかない。
左及び右の面を1個分面積を減らすには、1段分の箱を除去すればよい。

よって、各段連続して箱が置かれている数を求め、その数が小さい順にK個まで段を減らして行こう。
このような段々の形状において、各段の横幅は、スタックを使うテクで列挙できる。

段の数はO(max(A)*N)個有りうるので、愚直に保持しようとするとMLEする。
map等を使い、同じ横幅の段が何個あるかカウントするようにすると良い。
横幅のバリエーションはO(N)程度しかないので、こちらだとMLEしない。

int N;
ll K,A[101010],S,ret;
vector<pair<int,ll> > V;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) cin>>A[i], S+=A[i];
	ret += 2*S + N;
	
	vector<pair<ll,ll> > st;
	st.push_back({0,-1});
	FOR(i,N+1) {
		if(A[i]>st.back().first) {
			st.push_back({A[i],i});
		}
		else {
			while(st[st.size()-2].first>A[i]) {
				ll num=st.back().first-st[st.size()-2].first;
				ret += 2*num;
				V.push_back({i-st.back().second,num});
				st.pop_back();
			}
			ll num=st.back().first-A[i];
			ret += 2*num;
			V.push_back({i-st.back().second,num});
			st.back().first=A[i];
			
		}
	}
	
	ret -= 2*K;
	
	sort(ALL(V));
	FORR(r,V) {
		ll rem=min(r.second,K/r.first);
		ret -= 2*rem;
		K -= rem*r.first;
	}
	
	cout<<ret<<endl;
	
	
}

まとめ

今回のあさプロは難しかったのか、CDの回答者少ないね。