TCO2013 Round1B

TCO2013 Round1B

250
ソートして両端から取るだけ
500
縦の選び方を決めると横の選び方はgreedyに求まるのでビット全探索

int getMoves(vector <string> board, int R, int C) {
	int h=board.size(),w=board[0].size();
	int ans=INF;
	vector<int> b(h);
	rep(i,h){
		int m=0;
		rep(j,w)if(board[i][j]=='X')m|=1<<j;
		b[i]=m;
	}
	rep(i,1<<h){
		int m=0;
		for(int j=0;j<h;){
			if(i&1<<j){
				j+=R;
			}else {
				m|=b[j];
				j++;
			}
		}
		int s=0;
		rep(j,h)if(i&1<<j)s++;
		for(int j=0;j<w;){
			if(m&1<<j){
				s++;
				j+=C;
			}else j++;
		}
		ans=min(ans,s);
	}
	return ans;
}

1000
反転の操作は可逆だから例えばredotopcとodcpoterを同じ文字列にできる場合はそれぞれを操作して取り得る文字列の集合は等しくなる。また、可逆であることから異なる集合は必ず互いに素となる。よって集合毎の個数をカウントし奇数個となっている集合の個数が答えとなる。また、文字列は２文字ごとに見れば末尾からgreedyに当てはめて任意の順にソートでき、各集合は互いに素だから適当に正規化しておけば効率的にカウントできる。

int getMin(vector <string> words) {
	map<vector<pair<char,char> > ,int> mp;
	map<vector<pair<char,char> > ,int>::iterator it;
	rep(i,words.size()){
		string &s=words[i];
		vector<pair<char,char> > v;
		rep(j,s.size()/2){
			v.push_back(make_pair(min(s[j*2],s[j*2+1]),max(s[j*2],s[j*2+1])));
		}
		sort(v.begin(),v.end());
		if(s.size()&1){
			v.push_back(make_pair(s[s.size()-1],'\0'));
		}
		++mp[v];
	}
	int ans=0;
	for(it=mp.begin();it!=mp.end();++it){
		if(it->second&1)ans++;
	}
	return ans;
}