TopCoder SRM 518 DIV2
Rating: 962(緑)→975(緑)
サブミット速度も上げていかなければいけないと感じた。
1000が解けそうで解けなかった。doubleの挙動はよく分からない。
599.99 Point
250: TwiceString
#include <iostream> #include <sstream> #include <string> #include <vector> using namespace std; class TwiceString { public: string getShortest(string s) { for (int i = s.size() - 1; 0 <= i; --i) { const string com = s.substr(0, i); if (s.find(com, s.size() - i) != string::npos || i == 0) { return s + s.substr(i); } } return string("WA"); } };
207.56 Points
500: LargestSubsequence
#include <iostream> #include <sstream> #include <string> #include <vector> using namespace std; class LargestSubsequence { public: string getLargest(string s) { string res; s += 'a' - 1; vector<int> largest(s.size()); largest[largest.size() - 1] = s[s.size() - 1]; for (int i = largest.size() - 2; 0 <= i; --i) { if (s[i] > largest[i + 1]) largest[i] = s[i]; else largest[i] = largest[i + 1]; } for (int i = 0; i < (s.size() - 1); ++i) { if (s[i] >= largest[i]) res += s[i]; } return res; } };
こういうのの解法をちゃっちゃと思いつきたい。
392.43 Points
1000: CoinReversing
あとでデバッグした結果をのせる。
#include <iostream> #include <sstream> #include <string> #include <vector> #include <queue> using namespace std; class CoinReversing { public: double expectedHeads(int N, vector <int> a) { double head = (double)(N - a[0]) / N; for (int i = 1; i < a.size(); ++i) { head = head * ((double)(N - a[i]) / N) + (1.0 - head) * ((double)a[i] / N); } return N * head; } };
式を整理しただけで本当に通るようになった。小数誤差ぱない…