hotpepsiの練習帳

SRM 502 Div2

02:05

Easy (250) TheProgrammingContestDivTwo プログラミングコンテスト

N個のタスクが与えられる。それぞれ解くのにrequiredTime[i]の時間かかる。

解くとスコアが1増えてペナルティが経過時間tだけ増える。

T分の間に、スコアの最大値と、そのときのペナルティを返す。

requiredTimeを昇順にソートして加える。

#include <algorithm>
#include <string>
#include <vector>

using namespace std;
typedef vector <int> VI;

class TheProgrammingContestDivTwo {
	public:
	VI find(int T, VI requiredTime) {
		sort(requiredTime.begin(), requiredTime.end());
		int past = 0;
		int solved = 0;
		int penalty = 0;
		VI::const_iterator it;
		for (it = requiredTime.begin(); it != requiredTime.end(); ++it) {
			past += *it;
			if (past > T) {
				break;
			}
			++solved;
			penalty += past;
		}
		VI r;
		r.push_back(solved);
		r.push_back(penalty);
		return r;
	}
};

Medium (500) TheLotteryBothDivs 当たりくじ

9桁の数字のくじがあり、当たりくじのsuffixが与えられるとき、当たる確率を求める。

suffixをprefixと考えても同じなので、suffix文字列を逆順にすることで、suffixをprefixに変換した。

prefixの小さい桁から順番に確率を加えていく。

桁数の小さいprefixは桁数の大きいprefixを含むので、より大きいprefixの中に処理中のprefixを含むものがあれば、無効にする。

#include <algorithm>
#include <string>
#include <vector>
#include <set>

using namespace std;
typedef vector<string> StringVector;
typedef set<string> StringSet;

class TheLotteryBothDivs {
	public:
	double find(vector <string> goodSuffixes) {
		StringSet seq[10];	// use 1 to 9
		StringVector::const_iterator it;
		for (it = goodSuffixes.begin(); it != goodSuffixes.end(); ++it) {
			if (it->length() >= 1 && it->length() <= 9) {
				string s = *it;
				reverse(s.begin(), s.end());
				seq[it->length()].insert(s);
			}
		}

		double result = 0.0;
		double rate = 0.1;
		for (int i = 1; i <= 9; ++i) {
			StringSet::const_iterator it;
			for (it = seq[i].begin(); it != seq[i].end(); ++it) {
				result += rate;
				for (int j = i + 1; j <= 9; ++j) {
					StringSet::iterator temp;
					while (true) {
						temp = seq[j].lower_bound(*it);
						if (temp == seq[j].end() || strncmp(it->c_str(), temp->c_str(), it->length()) != 0) {
							break;
						}
						seq[j].erase(temp);
					}
				}
			}
			rate /= 10.0;
		}

		return result;
	}
};

Hard (1000) TheCowDivTwo 逃げた牛のカウント

0からN-1まで番号がついたN匹の牛のうち、K匹が逃げた。

逃げた牛の番号を合計するとNで割り切れるとき、可能な牛の組み合わせの場合の数を求めよ。

なんかもやもやしてわからなかったので、ぐぐって解法を調べた。

nまでの番号がついた牛が(1～47)匹逃げたときの場合の数を求めておき、(n+1)までの番号がついた牛が逃げたときの場合の数を、そこからの差分で求めていく。

面倒だったのでstaticの二次元配列。

#include <string>
#include <vector>
using namespace std;
class TheCowDivTwo {
	public:
	int find(int N, int K) {
		static int current[47][1024];
		memset(current, 0, sizeof(current));
		current[0][0] = 1;
		for (int n = 0; n < N; ++n) {
			static int prev[47][1024];
			memcpy(prev, current, sizeof(current));
			for (int p = 1; p <= K; ++p) {
				for (int m = 0; m < N; ++m) {
					int mod = (m + n) % N;
					current[p][mod] += prev[p - 1][m];
					current[p][mod] %= 1000000007;
				}
			}
		}
		int result = current[K][0];
		return result;
	}
};