TopCoder SRM 554 Div1 Medium TheBrickTowerMediumDivOne

問題

n個の建物があり、それぞれの高さはheights[i]である。
この建物を一列に並べるが、隣合う建物同士の距離は、隣合う建物のうち大きいほうの高さでなくてはならない。

列の端から端までの距離が最小になるような並べ方のうち、
辞書順で最小のものを求めよ。

制約条件

n≦47
heights[i]≦47

方針

まず、建物の高さが全て異なる場合を考える。
建物の間はn-1個ある。
n番目に大きい建物〜2番目に大きい建物の高さは、距離として使わなければならない。

建物を小さい順に、今までに置いた建物の右端か左端に建物を次々に置いていく、
という操作を繰り返すと、うまく並べられる。
また、この他に上手い並べ方は存在しない。
（なぜなら、高い建物が低い建物の間に割り込むと、その時点で最適でなくなるから）

右か左に置くかであるが、これは辞書順で良いほうを貪欲で選べばよい。

次に、同じ建物が複数あるときを考える。
○を新しく置く建物、●を今まで置いた建物とすると、
○●●●●○○のように、新しい建物の列のどこかに今まで置いた建物を割り込ませたものが、全て最適解になっていることがわかる。

○は辞書順で最小に並べるのが明らかに最適で、
●の位置は、入れる場所を全通り試して、最もよいものを取ればよい。

ソースコード

class TheBrickTowerMediumDivOne {
	public:
	vector <int> find(vector <int> heights) {
		int n = heights.size();
		vector<pi> v;
		vi ans;
		rep(i, n) v.pb(mp(heights[i], i));
		sort(all(v));
		
		rep(i, n){
			vi tmp;
			for(int j = i; j < n && v[j].first == v[i].first; j++) tmp.pb(v[j].second);
			i += tmp.size() - 1;
			
			vi next;
			rep(j, tmp.size() + 1){
				vi cand = tmp;
				cand.insert(cand.begin() + j, all(ans));
				if(next.empty() || next > cand) next = cand;
			}
			ans = next;
		}
		return ans;
	}
};