TopCoder SRM 620 Div1 Medium CandidatesSelection

本番色々反省するところがある問題。
http://community.topcoder.com/stat?c=problem_statement&pm=13144

問題

0～(N-1)番の従業員がおり、初期状態でこの順番で並んでいる。
各従業員はM種類のスキルにおける能力値を持つ。

この従業員を以下の手順で並べ替えることができる。

• M種類のスキルのいずれかを選択する。
• 従業員を選んだスキルの優れた順で並べ替える。ただし同着の場合はその前の並び順を保持する。

並べ替えを任意回実行可能な時、最終的に指定された並び順にできるか答えよ。

解法

並べ替えを１回行うと、基本的にはそれまでの並びは関係なく並び替えられる。
ただし例外として、能力値が同着の場合にはそれまでの並びを保持される。
よって戦略としては、「最後の並べ替えを行う前に、同着の能力どうしの従業員は事前に目標の並び順にしておく。それ以外は最後の並べ替えで適切な場所に行くのでどうでもよい」となる。

この推論より、最終的な並び順から、巻き戻していくことを考える。
初期状態を、従業員是全員が最終的な並び順で並んだ１つのグループにいると考える。

もし各グループにおいて、従業員が昇順に並んでいるならそれ以上巻き戻す必要はなく、成功である。
それ以外の場合、１手巻き戻すことを考える。
各並べ替え候補において、順位に矛盾が起こる並べ変え、すなわちグループ内の従業員が目標の並び順と異なる並び順になる並べ替えは選択できない。

矛盾が起きない並べ替えを発見したら、その並べ替えで同着にならない従業員同士は別グループにして再帰的に巻き戻しを行う。

class CandidatesSelection {
	public:
	int M;
	vector<string> S;
	
	int dfs(vector<vector<int> > V, ll mask) {
		int i,x,y;
		int ng=0;
		FOR(i,V.size()) FOR(x,V[i].size()-1) ng+=V[i][x]>V[i][x+1];
		if(ng==0) return 1;
		
		FOR(i,M) if((mask&(1LL<<i))==0) {
			int ng=0;
			vector<vector<int> > V2;
			FOR(x,V.size()) {
				map<int,vector<int> > MM;
				FOR(y,V[x].size()-1) if(S[V[x][y]][i]>S[V[x][y+1]][i]) ng=1;
				FOR(y,V[x].size()) MM[S[V[x][y]][i]].push_back(V[x][y]);
				if(ng) break;
				ITR(it,MM) if(it->second.size()>1) V2.push_back(it->second);
			}
			if(ng==0 && V2!=V) return dfs(V2,mask|(1LL<<i));
		}
		return 0;
	}
	
	string possible(vector <string> score, vector <int> result) {
		S=score;
		M=score[0].size();
		
		vector<vector<int> > V;
		V.push_back(result);
		if(dfs(V,0)) return "Possible";
		return "Impossible";
	}
}

まとめ

本番、巻き戻しまでは思いついたのだが、グループ別に異なる巻き戻し手順を取るコードを書いてミスした。
異なるグループも含めて同じ並べ替え手段を使って巻き戻さないといけないよね…。