TopCoder SRM 420 DIV 2
| Problem | Check | Points |
| 250 | ○ | 235.02 |
| 500 | ○ | 268.82 |
| 1000 | - | - |
全部実装問題、面白くない。
1000の上5桁をlog10を使って求める、というところだけは勉強になりました。
TopCoder Statistics: SRM 420 Problem Set & Analysis
Problem 250 DeckRearranging
問題
We have a deck of cards. Each of the cards is either black or red. We will use the character B to represent a black card and the character R for a red card. By listing the cards from top to bottom of the deck we get a String deck.
We now want to insert all the cards into a new deck. Initially, the new deck is empty. We will now process the cards in the old deck from top to bottom. When processing the card that corresponds to character i of deck, take it from the old deck and insert it into the new deck in such a way that exactly above[i] cards are above it after the insertion.
Write a method that takes the String deck and int[] above, and returns the new deck encoded as a String in the same way as deck.
My code
vector<char> insert(vector<char> v, char c, int n){ vector<char> ans; for(int i=0 ; i<n ; i++){ ans.push_back(v[i]); } ans.push_back(c); for(int i=n ; i<v.size(); i++){ ans.push_back(v[i]); } return ans; } string vectorToString(vector<char> v){ string s; for(int i=0 ; i<v.size() ; i++){ s += v[i]; } return s; } class DeckRearranging { public: string rearrange(string deck, vector <int> above) { vector<char> v; string s; for(int i=0 ; i<deck.size() ; i++){ v = insert(v, deck[i], above[i]); } return vectorToString(v); } };
Problem 500 YearProgressbar
問題
You are a big fan of New Year's Eve parties. The next one is not too far away, and you are already looking forward to it.
Then, one day, you wake up with a question: "Wait a moment, exactly how far away is it?"
To answer this question, you decided to implement a simple application: a year progress bar that will always show how much of the current year has already passed.
In this problem, your goal is to implement the most important part of this application: a function that gets a String currentDate, and returns the elapsed part of the year, as a percentage.
The variable currentDate will be of the form "Month DD, YYYY HH:MM" (quotes for clarity). Here, "Month" is the name of the current month, "YYYY" is a four-digit number representing the current year, and "DD", "HH", and "MM" are two-digit numbers (possibly with a leading zero) that represent the current day, hour and minute.
My code
bool isLeap(int n){ if(n%400==0) return true; if(n%100==0) return false; if(n%4==0) return true; return false; } vector<string> split(const string& str, const string& delimiter) { // delimiter(2 文字以上も可) を空白に置換 string item(str); for(unsigned pos = item.find(delimiter); pos != string::npos; pos = item.find(delimiter, pos)) { item.replace(pos, delimiter.size(), " "); } // 分解 stringstream buf(item); // 読み取り vector<string> result; while(buf >> item) { result.push_back(item); } return result; } int toMonth(string s){ if(s=="January") return 1; else if(s=="February") return 2; else if(s=="March") return 3; else if(s=="April") return 4; else if(s=="May") return 5; else if(s=="June") return 6; else if(s=="July") return 7; else if(s=="August") return 8; else if(s=="September") return 9; else if(s=="October") return 10; else if(s=="November") return 11; else return 12; } ll calcTime(int month, int day, int hour, int minutes, bool leap){ ll time=0; if(month==1) time=0; else if(month==2) time=31; else if(month==3) time=59; else if(month==4) time=90; else if(month==5) time=120; else if(month==6) time=151; else if(month==7) time=181; else if(month==8) time=212; else if(month==9) time=243; else if(month==10) time=273; else if(month==11) time=304; else if(month==12) time=334; if(leap && month>=3) time++; time += day; time--; time = time*24*60 + hour*60 + minutes; return time; } class YearProgressbar { public: double percentage(string currentDate) { vector<string> v = split(currentDate, " ,"); v[1] = v[1].substr(0,2); vector<string> v2 = split(v[3],":"); int month = toMonth(v[0]); int day = atoi(v[1].c_str()); int year = atoi(v[2].c_str()); int hour = atoi(v2[0].c_str()); int minutes = atoi(v2[1].c_str()); return 100*(double)calcTime(month, day, hour, minutes, isLeap(year))/(double)calcTime(12,31,24,0,isLeap(year)); } };
Problem 1000 PrettyPrintingProduct
問題
You will be given two positive ints A and B.
Let C be the product of all integers between A and B, inclusive.
The number C has a unique representation of the form C = D * 10^E, where D and E are non-negative integers and the last digit of D is non-zero.
Write a method that will return the value of C formatted as a String of the form "D * 10^E" (quotes for clarity only). Substitute the actual values of D and E into the output. If D has more than 10 digits, only output the first five and the last five digits of D, and separate them by three periods.
My code
string llToString(ll n){
stringstream ss;
ss << n;
return ss.str();
}
// 5桁のstringになるように 上に0を挿入する。
string to5digit(string s){
if(s.size()==5) return s;
while(s.size()!=5){
s = "0"+s;
}
return s;
}
class PrettyPrintingProduct {
public:
string prettyPrint(int A, int B) {
int num2=0, num5=0;
// a -> 上5桁, b-> 下5桁(10桁を超えない場合は10桁まで)
ll a=0,b=1;
// 10桁を超えるかどうか
bool is10digit = false;
// 上5桁を求める
double log10ans = 0;
for(int i=A ; i<=B ; i++){
log10ans += log10(double(i));
}
log10ans -= (floor)(log10ans);
a = (ll)(pow(10,log10ans)*10000);
// 2と5の因数は保存しておき、
// 残りの数を b に掛けていく。
// bが10桁を超えた場合は 下5桁だけを保存する。
for(ll i=A ; i<=B ; i++){
ll k = i;
while(k%2==0){
k = k/2;
num2++;
}
while(k%5==0){
k = k/5;
num5++;
}
if(!is10digit){
b *= k;
if(b > 10000000000LL){
b = b%100000;
is10digit = true;
}
}
else b = (b*k)%100000;
}
// 10のD乗を求める。
int D=min(num2,num5);
num2 -= D;
num5 -= D;
ll mul;
// 2の因数、5の因数のうち、残ったものを掛けていく。
if(num2==0) mul = 5;
else mul = 2;
int num = max(num2, num5);
while(num >0){
if(!is10digit){
b *= mul;
if( b > 10000000000LL){
b = b%100000;
is10digit = true;
}
}
else b = (b*mul)%100000;
num--;
}
if(!is10digit) return llToString(b)+ " * 10^"+llToString(D);
return llToString(a) + "..." + to5digit(llToString(b)) + " * 10^" + llToString(D);
}
};
