2009-08-01
Quilting
SRM 160, Div2, Div2 Level-3, Div1, Div1 Level-2, Simulation |
キルト作り。自力で解けたが、解くのに一時間以上かかった。
class Quilting { public: string lastPatch(int length, int width, vector <string> colorList) { vector<vector<string> > quilt(200,vector<string>(200,string("."))); map<string,int> prevCount; int y=100, x=100, dir=0; quilt[y][x] = colorList[0]; prevCount[colorList[0]]++; for (int i = 1; i < length*width; i++) { const static int NEIGHBORS = 8; const static int nd[NEIGHBORS][2] = { {-1,-1}, {-1, 0}, {-1, 1}, { 0,-1}, { 0, 1}, { 1,-1}, { 1, 0}, { 1, 1} }; const static int MOVE_KINDS = 4; const static int mvd[MOVE_KINDS][4] = { {-1, 0, 0,-1}, { 0,-1, 1, 0}, { 1, 0, 0, 1}, { 0, 1,-1, 0} }; y += mvd[dir][0]; x += mvd[dir][1]; map<string,int> neighorCount; for (int j = 0; j < NEIGHBORS; j++) { const int dy = y + nd[j][0]; const int dx = x + nd[j][1]; if (quilt[dy][dx] != ".") { neighorCount[quilt[dy][dx]]++; } } string color; int minSameColor = INT_MAX; if (neighorCount.size() == colorList.size()) { for (map<string,int>::const_iterator itr = neighorCount.begin(); itr != neighorCount.end(); itr++) { if (itr->second < minSameColor) { color = itr->first; minSameColor = itr->second; } else if (itr->second == minSameColor) { if (prevCount[itr->first] < prevCount[color]) { color = itr->first; } else if (prevCount[itr->first] == prevCount[color]) { if (find(colorList.begin(),colorList.end(),itr->first) < find(colorList.begin(),colorList.end(),color)) { color = itr->first; } } } } } else { for (int j = 0; j < colorList.size(); j++) { if (neighorCount.find(colorList[j]) == neighorCount.end()) { if (prevCount[colorList[j]] < minSameColor) { minSameColor = prevCount[colorList[j]]; color = colorList[j]; } } } } quilt[y][x] = color; prevCount[color]++; if (quilt[y+mvd[dir][2]][x+mvd[dir][3]] == ".") { dir = (dir+1) % MOVE_KINDS; } } return quilt[y][x]; } };
Intersect
SRM 160, Div2, Div2 Level-2, Geometry |
全ての矩形に囲まれる矩形の面積を求める。
class Intersect { public: int area(vector <int> x, vector <int> y) { int left =INT_MIN, right=INT_MAX; int upper=INT_MIN, lower=INT_MAX; for (int i = 0; i < x.size(); i += 2) { if (x[i] > x[i+1]) swap(x[i], x[i+1]); if (y[i] > y[i+1]) swap(y[i], y[i+1]); left = max(left, x[i]); right = min(right, x[i+1]); upper = max(upper, y[i]); lower = min(lower, y[i+1]); } if ((right-left) <= 0 || (lower-upper) <= 0) return 0; else return (right-left) * (lower-upper); } };
Substitute
SRM 160, Div2, Div2 Level-1, String Manipulation |
コードがはみ出るので、ブログのデザインを横幅が広いデザインに変更した。
1文字ごとの復号。
class Substitute { public: int getValue(string key, string code) { map<char,int> decoder; for (int i = 0; i < key.length(); i++) { if (i == key.length()-1) decoder[key[i]] = 0; else decoder[key[i]] = i+1; } int value = 0; for (int i = 0; i < code.length(); i++) { if (decoder.find(code[i]) != decoder.end()) { value *= 10; value += decoder[code[i]]; } } return value; } };
コメントを書く
トラックバック - http://topcoder.g.hatena.ne.jp/caligue/20090801
リンク元
- 14 https://www.google.co.jp/
- 8 http://topcoder.g.hatena.ne.jp/
- 6 https://www.google.com/
- 5 http://topcoder.g.hatena.ne.jp/diarylist
- 4 http://twitturls.com/
- 2 http://topcoder.g.hatena.ne.jp/suztomo/20090802/1249175693
- 2 https://www.google.co.jp
- 2 http://search.yahoo.co.jp/
- 2 https://www.google.com.tw/
- 1 http://www.google.com/search?hl=en&q=topcoder+srm+445+div1&aq=f&oq=&aqi=