2009-08-27
FryingHamburgers
SRM 159, Div1, Div1 Level-1, Math, cheated, 30% |
すべてのハンバーガーを焼くのにかかる時間。解けなくて、さんざん悩んで、Editorialを見て、数学の問題だと気づいた。
75.0/250
class FryingHamburgers { public: int howLong(int panSize, int hamburgers) { if (hamburgers == 0) return 0; if (hamburgers <= panSize) return 10; return 5*(int)ceil(2.0*hamburgers/panSize); } };
コメントを書く
2009-07-28
ThePriceIsRight
SRM 159, Div2, Div2 Level-3, Div1, Div1 Level-2, Dynamic Programming |
Longest increasing sub sequence を求める問題。再帰を使って解く方法は思いついたが、それでは計算量が問題になるとわかり、結局やはりEditorialを見た。dynamic programming による方法で解ける。
class ThePriceIsRight { public: vector <int> howManyReveals(vector <int> prices) { const int size = prices.size(); vector<int> S(size,0), L(size,0); vector <int> result(2,0); for (int i = 0; i < size; i++) { int tmp = 0; for (int j = 0; j < i; j++) { if (prices[j] < prices[i]) tmp = max(tmp, S[j]); } for (int j = 0; j < i; j++) { if (S[j] == tmp && prices[j] < prices[i]) L[i] += L[j]; } if (L[i] == 0) L[i] = 1; S[i] = 1 + tmp; } result[0] = *max_element(S.begin(), S.end()); for (int i = 0; i < size; i++) { if (S[i] == result[0]) result[1] += L[i]; } return result; } };
Sets
SRM 159, Div2, Div2 Level-2, Math |
集合演算。
class Sets { public: vector <int> operate(vector <int> A, vector <int> B, string operation) { sort(A.begin(), A.end()); sort(B.begin(), B.end()); if (operation == "UNION") { return union_set(A, B); } else if (operation == "INTERSECTION") { return intersection(A, B); } else if (operation == "SYMMETRIC DIFFERENCE") { return symmetric_difference(A, B); } else { return vector<int>(); } } private: vector<int> union_set(const vector<int>& A, const vector<int>& B) { set<int> tmp_union; for (int i = 0; i < A.size(); i++) tmp_union.insert(A[i]); for (int i = 0; i < B.size(); i++) tmp_union.insert(B[i]); vector<int> ret; for (set<int>::const_iterator itr = tmp_union.begin(); itr != tmp_union.end(); itr++) ret.push_back(*itr); return ret; } vector<int> intersection(const vector<int>& A, const vector<int>& B) { int i=0, j=0; vector<int> ret; while (i<A.size() && j<B.size()) { if (A[i] == B[j]) { ret.push_back(A[i]); i++; j++; } else if (A[i] < B[j]) { i++; } else { j++; } } return ret; } vector<int> symmetric_difference(const vector<int>& A, const vector<int>& B) { vector<int> uni = union_set(A, B); vector<int> inter = intersection(A, B); vector<int> ret; for (int i = 0; i < uni.size(); i++) { if (find(inter.begin(),inter.end(),uni[i]) == inter.end()) ret.push_back(uni[i]); } return ret; } };
StreetParking
SRM 159, Div2, Div2 Level-1, Simple Search, Iteration, String Manipulation |
道に駐車できるかどうか。
class StreetParking { public: int freeParks(string street) { const int len = street.length(); int total = 0; for (int i = 0; i < len; i++) { if (street[i] != '-') continue; if (i+2 < len && street[i+2]=='B') continue; if (i+1 < len && (street[i+1]=='B'||street[i+1]=='S')) continue; if (i-1 >= 0 && street[i-1]=='S') continue; total++; } return total; } };