TopCoder SRM 811 : Div1 Easy Div2 Hard ReconstructPermutation

久々にHighest更新できてよかった。
https://community.topcoder.com/stat?c=problem_statement&pm=17129&rd=18802

問題

0～(N-1)のPermutationがあった。
そのうち部分列が与えられる。

この部分列を含むPermutationのうち、辞書順最小のものを求めよ。

解法

部分列に含まれない値については、与えられる部分列のうち自身より大きな値のものの直前に挿入しよう。
そのようなものがなければ末尾で。
O(N^3)でも通りそうな入力量だが、O(N)でも書ける。

class ReconstructPermutation {
	public:
	vector <int> reconstruct(int N, vector <int> partial) {
		set<int> alive;
		int i;
		FOR(i,N) alive.insert(i);
		FORR(a,partial) alive.erase(a);
		vector<int> ret;
		FORR(a,partial) {
			while(alive.size()&&*alive.begin()<a) {
				ret.push_back(*alive.begin());
				alive.erase(alive.begin());
			}
			ret.push_back(a);
		}
		while(alive.size()) {
			ret.push_back(*alive.begin());
			alive.erase(alive.begin());
		}
		return ret;
		
		
	}
}

まとめ

Div2だと800ptだし、運営側も普段のEasyより簡単な問題として認識してそうだね。