2009-08-30
MineField
SRM 169, Div1, Div1 Level-1, String Manipulation, 90% |
マインスイーパ。
225.69/250
class MineField { public: vector <string> getMineField(string mineLocations) { const static int SIZE = 9; vector <string> result(SIZE,string(SIZE,'0')); istringstream iss(mineLocations); char pad; int y, x; while (iss >> pad >> y >> pad >> x >> pad) result[y][x] = 'M'; const static int d[8][2] = { {-1,-1}, {-1, 0}, {-1, 1}, { 0,-1}, { 0, 1}, { 1,-1}, { 1, 0}, { 1, 1} }; for (y = 0; y < SIZE; y++) for (x = 0; x < SIZE; x++) { if (result[y][x] == 'M') continue; int counter = 0; for (int i = 0; i < 8; i++) { int dy = y + d[i][0]; int dx = x + d[i][1]; if (0<=dy&&dy<SIZE && 0<=dx&&dx<SIZE && result[dy][dx] == 'M') counter++; } result[y][x] += counter; } return result; } };
コメントを書く
2009-08-11
FairWorkload
SRM 169, Div2, Div2 Level-3, Div1, Div1 Level-2, Brute Force, 55% |
仕事をなるべく均等になるように割り振る。良問。Level-2の問題より解きやすかった。
532.87/1000 - 00:32:37
class FairWorkload { public: int getMostWork(vector <int> folders, int workers) { amounts = vector<int>(workers, 0); maxOptimalAmount = INT_MAX; go(folders, 0, workers, 0); return maxOptimalAmount; } private: int maxOptimalAmount; vector<int> amounts; void go(const vector<int>& folders, const int f_id, const int workers, const int w_id) { if (f_id == folders.size()) { for (int i = 0; i < workers; i++) if (amounts[i] == 0) return; maxOptimalAmount = min(maxOptimalAmount, *max_element(amounts.begin(),amounts.end())); return; } if (maxOptimalAmount <= amounts[w_id]) return; if (w_id == workers) return; amounts[w_id] += folders[f_id]; go(folders, f_id+1, workers, w_id); amounts[w_id] -= folders[f_id]; if (w_id+1 == workers) return; amounts[w_id+1] += folders[f_id]; go(folders, f_id+1, workers, w_id+1); amounts[w_id+1] -= folders[f_id]; } };
Twain
SRM 169, Div2, Div2 Level-2, String Manipulation, failed, 35% |
問題文の通りに文字列を変換する。やるだけの問題だが、書く必要があるコード量が多い。一回目にサブミットしたプログラムはバグがあり、システムテストは通らなかった。
184.88/500 - 00:42:14 (failed)
class Twain { public: string getNewSpelling(int year, string phrase) { vector<char> exceptions; exceptions.push_back('a'); exceptions.push_back('e'); exceptions.push_back('i'); exceptions.push_back('o'); exceptions.push_back('u'); for (int y = 1; y <= year; y++) { string tmpStr; int len; switch (y) { case 1: if (phrase[0] == 'x') phrase[0] = 'z'; phrase = replaceCharsOfWord(phrase, " x", " z"); phrase = replaceCharsOfWord(phrase, "x", "ks"); break; case 2: phrase = replaceCharsOfWord(phrase, "y", "i"); break; case 3: phrase = replaceCharsOfWord(phrase, "ce", "se"); phrase = replaceCharsOfWord(phrase, "ci", "si"); break; case 4: do { tmpStr = phrase; phrase = replaceCharsOfWord(phrase, "ck", "k"); } while (tmpStr != phrase); break; case 5: if (phrase.substr(0,3) == "sch") phrase = "sk" + phrase.substr(3); phrase = replaceCharsOfWord(phrase, " sch", " sk"); phrase = replaceCharsOfWord(phrase, "chr", "kr"); for (char c = 'a'; c <= 'z'; c++) { if (c == 'h') continue; string pattern("c"+string(1,c)); string placement("k"+string(1,c)); phrase = replaceCharsOfWord(phrase, pattern, placement); } phrase = replaceCharsOfWord(phrase, "c ", "k "); len = phrase.length(); if (phrase[len-1] == 'c') phrase[len-1] = 'k'; break; case 6: if (phrase.substr(0,2) == "kn") phrase = "n" + phrase.substr(2); phrase = replaceCharsOfWord(phrase, " kn", " n"); break; case 7: do { tmpStr = phrase; for (char c = 'a'; c <= 'z'; c++) { if (find(exceptions.begin(),exceptions.end(),c) == exceptions.end()) { string pattern(2,c); string placement(1,c); phrase = replaceCharsOfWord(phrase, pattern, placement); } } } while (tmpStr != phrase); break; } } return phrase; } private: string replaceCharsOfWord(const string& phrase, const string pattern, const string placement) { string result; string::size_type pos = 0; string::size_type pre_pos = 0; string::size_type pat_len = pattern.length(); while ((pos = phrase.find(pattern,pos)) != string::npos) { result.append(phrase, pre_pos, pos-pre_pos); result.append(placement); pos += pat_len; pre_pos = pos; } result.append(phrase, pre_pos, phrase.length()-pre_pos); return result; } };
Swimmers
SRM 169, Div2, Div2 Level-1, Simple Math, 90% |
川を往復するのに必要な時間を求める。
224.03/250 - 00:10:06
class Swimmers { public: vector <int> getSwimTimes(vector <int> distances, vector <int> speeds, int current) { const int numSwimmers = distances.size(); vector <int> result(numSwimmers); for (int i = 0; i < numSwimmers; i++) { if (distances[i] == 0) { result[i] = 0; } else if (current >= speeds[i]) { result[i] = -1; } else { result[i] = static_cast<int>( static_cast<double>(distances[i]) / (speeds[i]-current) + static_cast<double>(distances[i]) / (speeds[i]+current)); } } return result; } };
Olivia2011/07/09 22:49Ppl like you get all the birans. I just get to say thanks for he answer.
cganpmvkaa2011/07/10 00:21ozUmeq <a href="http://pjfcqeeeqmnr.com/">pjfcqeeeqmnr</a>
gkbfwfvcb2011/07/10 21:09Bo1aDa , [url=http://xrkdnugczyzj.com/]xrkdnugczyzj[/url], [link=http://sbngsfqxhlpy.com/]sbngsfqxhlpy[/link], http://safjlfwoassi.com/
uxpnpuna2011/07/11 20:32crHIwv <a href="http://fodsgqzsvyim.com/">fodsgqzsvyim</a>
mhhaau2011/07/12 21:58da56vU , [url=http://tqvvgrxdnlwt.com/]tqvvgrxdnlwt[/url], [link=http://ofcuaexemicz.com/]ofcuaexemicz[/link], http://shzifphpejdh.com/