TopCoder SRM 496 Div2

プログラミング

時間切れになって500をsubmitできなかったけど、解けるには解けたので。

Easy

問題

アナグラムになって無いやつを数えろー^0^

解法

2つの異なる文字列をそれぞれの文字列の文字を昇順にソートし比較したとき等しければ2つの異なる文字列はアナグラム。
後はstd::mapにセットしていって、sizeを返せばよい。
でもセットするだけならstd::mapじゃなくてstd::setでもできるので、やってみた。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

class AnagramFree{
public:
	static int getMaximumSubset(vector <string> S){
		std::set<string> ana;
		for(int i=0; i<S.size(); ++i){
			sort(S[i].begin(), S[i].end());
			ana.insert(S[i]);
		}
		return ana.size();
	}
};


int main(int argc, char**argv){	
	vector<string> ana; // example3 {"creation","sentence","reaction","sneak","star","rats","snake"}
	ana.push_back("creation");
	ana.push_back("sentence");
	ana.push_back("reaction");
	ana.push_back("sneak");
	ana.push_back("star");
	ana.push_back("rats");
	ana.push_back("snake");
	cout << "ret:" << AnagramFree::getMaximumSubset(ana) << endl;
}

ret:4

Medium

問題

縦にだけ引ける青の線と、横にだけ引ける赤の線を使って、用意された絵を描くのに必要な線を引く最小回数を答えてね。
ちなみに青と赤の線は交差すると緑になるよ。

解法

TopCoderらしくないと勝手に思って途中で止めた力押し。
system test通るかわからんけど:P

#include <iostream>
#include <string>
#include <vector>

using namespace std;

class ColoredStrokes{
	static const int RED = 0x01;
	static const int BLUE = 0x02;
	static const int GREEN= RED|BLUE;
	static const int EMPTY= 0x00;
public:
	static int getLeast(vector <string> picture){
		int ret = 0;
		vector< vector<int> > n(picture.size());
		
		for(int i=0; i<picture.size(); ++i){
			n[i].resize(picture[i].size());
			for(int j=0; j<picture[i].size(); ++j){
				switch(picture[i][j]){
					case 'R':
						n[i][j] = RED;
						break;
					case 'B':
						n[i][j] = BLUE;
						break;
					case 'G':
						n[i][j] = GREEN;
						break;
					case '.':
					default:
						n[i][j] = EMPTY;
						break;
				}
			}
		}
		
		bool loop = true;
		while(loop){
			loop = false;
			for(int i=0; i<picture.size(); ++i){
				for(int j=0; j<picture[i].size(); ++j){
					if(n[i][j] & RED){
//						cout << "RED:" << i << "," << j << endl;
						for(int x=j; x<picture[i].size() && n[i][x]&RED; ++x) n[i][x] &= ~RED;
						ret++;
						loop = true;
					}
					if(n[i][j] & BLUE){
//						cout << "BLUE:" << i << "," << j << endl;
						for(int y=i; y<picture.size() && n[y][j]&BLUE; ++y) n[y][j] &= ~BLUE;
						ret ++;
						loop = true;
					}
				}
			}
		}
		return ret;
	}
};


int main(int argc, char**argv){
	vector<string> s;
	
	s.push_back("GR"); // example5 {"GR", "BG"} Returns 4
	s.push_back("BG");
	cout << "ret:" << ColoredStrokes::getLeast(s) << endl;
}


他に見たのは赤の線と青の線の数を数えていきながら、絵を白で塗りつぶしていく方法があった。
こっちのほうがよさそう。メモリも取らないし。
というわけで、それをリスペクトしたのが以下。

class ColoredStrokes{
public:
	static int getLeast(vector <string> picture){
		int ret = 0;
		for(int i=0; i<picture.size(); ++i){
			for(int j=0; j<picture[i].size(); ++j){
				switch(picture[i][j]){
					case 'R':
						for(int x=j; j<picture[i].size(); ++x){
							if(picture[i][x] == 'G'){ picture[i][x] = 'B'; }
							else if(picture[i][x] == 'R'){ picture[i][x] = '.'; }
							else { break; }
						}
						ret += 1;
						break;
					case 'B':
						for(int y=i; y<picture.size(); ++y){
							if(picture[y][j] == 'G'){ picture[y][j] = 'R'; }
							else if(picture[y][j] == 'B'){ picture[y][j] = '.'; }
							else { break; }
						}
						ret += 1;
						break;
					case 'G':
						for(int x=j; j<picture[i].size(); ++x){
							if(picture[i][x] == 'G'){ picture[i][x] = 'B'; }
							else if(picture[i][x] == 'R'){ picture[i][x] = '.'; }
							else { break; }
						}
						for(int y=i; y<picture.size(); ++y){
							if(picture[y][j] == 'G'){ picture[y][j] = 'R'; }
							else if(picture[y][j] == 'B'){ picture[y][j] = '.'; }
							else { break; }
						}
						ret += 2;
						break;
					case '.':
					default:
						break;
					
				}
			}
		}
		return ret;
	}
};

System Testとおして無いからわからんけど、exampleは全部通ったから大丈夫だとおもいたい。
もっときれいな解決方法がありそうだなぁ、これ。