TopCoder SRM 620, Division 2, Level 1 : CandidatesSelectionEasy

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=13160&rd=15853

概要

　きつねのしえるは新しいメイドさんを雇おうとしている。メイドさん候補は n 人いて、0 から n - 1 に番号付けされている。また、メイドさんに要求される技能は m 種類あり、0 から m - 1 に番号付けされている。
　今、しえるは各メイドさん候補のそれぞれの技能レベルの評価を終えていて、i 番のメイドさん候補の j 番の技能は score[ i ][ j ] として与えられる。
　しえるは x 番の技能が最も大切だと考えている。そこで、メイドさん候補を x 番の技能が高い順に並び替えた表を作成して欲しい。x 番の技能レベルが同じ場合は、番号の若いメイドさん候補を上位とせよ。

解法

　0 ... n - 1 を昇順に含む配列を作ってから、それぞれの番号に対応するメイドさん候補の x 番の技能レベルをキーにソートすることを考えます。このとき、技能レベルが等しい場合の条件から、安定ソートをする必要がありますが、C++ には std::stable_sort があるのでこの点は大丈夫です。
　解法は「 0 ... n - 1 を作って安定ソート」でほぼ完結しているので、短く実装する技法について書いておきます。

1. 0 ... n - 1 の配列を作る : サイズ n の配列を確保して std::iota
2. score の情報を使って安定ソート : std::stable_sort の第三引数（比較用ファンクタ）に score をキャプチャしたラムダ式を渡す

コード

using VI = vector<int>;

#define ALL( c ) (c).begin(), (c).end()

class CandidatesSelectionEasy
{
public:
	vector <int> sort( vector <string> score, int x )
	{
		const int N = score.size();

		VI res( N );
		iota( ALL( res ), 0 );
		stable_sort( ALL( res ), [&]( const int a, const int b ){ return score[a][x] < score[b][x]; } );
		
		return res;
	}
};