TopCoderOpen Round 1A 1000点問題

解法

枝刈りしつつ全探索する．

実装(C++)

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <deque>
#include <complex>
#include <string>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <valarray>
#include <iterator>
using namespace std;

typedef long long int lli;
typedef unsigned int uint;
typedef unsigned char uchar;
typedef unsigned long long ull;

#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define RREP(i,x) for(int i=(x);i>=0;i--)
#define RFOR(i,c) for(__typeof((c).rbegin())i=(c).rbegin();i!=(c).rend();i++)
bool comp(const string &a,const string &b){
	int _a=0,_b=0;
	REP(i,a.size()){
		if(a[i]=='Y')_a++;
		if(b[i]=='Y')_b++;
	}
	return _a>_b;
}
int C,R;
int answer=51;
vector<int> remain_column;
vector<bool> used_column;
vector<bool> used;
string s;
vector<string> matrix;
void doIt(const string &a){
	for(int i=0;i<(int)a.size();i++){
		if((s[i]=='Y')^(a[i]=='Y')){
			s[i]='Y';
		}else{
			s[i]='N';
		}
	}
}
void dfs(int count){
	int tar=-1,minimum=99;
	vector<int> cr;
	//列について一番小さいものを求める
	for(int i=0;i<C;i++){
		if(remain_column[i]==0){
			if(s[i]=='Y')return;
			used_column[i]=true;
			cr.push_back(i);
		}else{
			if(minimum>remain_column[i]){
				minimum=remain_column[i];
				tar=i;
			}
		}
	}
	if(tar==-1){
		answer=min(answer,count);
		REP(i,cr.size())used_column[cr[i]]=false;
		return;
	}
	//含まれるものを確定する
	vector<int> cc;
	REP(i,R){
		if(used[i])continue;
		if(matrix[i][tar]=='Y'){
			cc.push_back(i);
			used[i]=true;
			REP(j,C){
				if(matrix[i][j]=='Y')remain_column[j]-=1;
			}
		}
	}
	if(s[tar]=='Y'){
		REP(i,cc.size()){
			doIt(matrix[cc[i]]);
			dfs(count+1);
			doIt(matrix[cc[i]]);
		}
	}else{
		dfs(count);
		if(cc.size()>1){
			REP(i,cc.size()){
				doIt(matrix[cc[i]]);
			}
			dfs(count+2);
			REP(i,cc.size()){
				doIt(matrix[cc[i]]);
			}
		}
	}

	REP(i,cr.size())used_column[cr[i]]=false;
	REP(k,cc.size()){
		int i=cc[k];
		used[i]=false;
		REP(j,C){
			if(matrix[i][j]=='Y')remain_column[j]+=1;
		}
	}
	return;
}
class EllysLights {
public: int getMinimum(string initial, vector<string> switches) {
	sort(switches.begin(),switches.end());
	switches.erase(unique(switches.begin(),switches.end()),switches.end());
	stable_sort(switches.begin(),switches.end(),comp);
	cout<<initial<<endl;
	cout<<"---"<<endl;
	REP(i,switches.size()){
			cout<<switches[i]<<endl;
	}
	remain_column=vector<int>(initial.size());
	C=initial.size();
	R=switches.size();
	for(int i=0;i<C;i++){
		for(int j=0;j<R;j++){
			if(switches[j][i]=='Y')remain_column[i]++;
		}
	}
	used=vector<bool>(R,false);
	used_column=vector<bool>(C,false);
	answer=51;
	matrix=switches;
	s=initial;
	dfs(0);
	if(answer>50)answer=-1;
	return answer;
}
};