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;
	}
};

式を整理しただけで本当に通るようになった。小数誤差ぱない…