Hatena::Grouptopcoder

nodchipのTopCoder日記 このページをアンテナに追加 RSSフィード

 | 

2013-11-25

Facebook Hacker Cup 2014 Qualification Round 00:39 Facebook Hacker Cup 2014 Qualification Round - nodchipのTopCoder日記 を含むブックマーク はてなブックマーク - Facebook Hacker Cup 2014 Qualification Round - nodchipのTopCoder日記 Facebook Hacker Cup 2014 Qualification Round - nodchipのTopCoder日記 のブックマークコメント

20: Square Detector

  • なんか面倒そう・・・
  • ・・・
  • あれ?上下左右の座標のminmaxしらべて中身が全部塗られていることを確認しておしまい?
  • Accepted
bool black[32][32];
int minC = INT_MAX;
int maxC = INT_MIN;
int minR = INT_MAX;
int maxR = INT_MIN;
bool solve() {
	if (minC == INT_MAX){
		return false;
	}
	
	if (maxC - minC != maxR - minR){
		return false;
	}

	for (int r = minR; r <= maxR; ++r) {
		for (int c = minC; c <= maxC; ++c){
			if (!black[r][c]) {
				return false;
			}
		}
	}

	return true;
}

int main() {
	std::ios::sync_with_stdio(false);

	int T;
	cin >> T;
	for (int testCase = 1; testCase <= T; ++testCase){
		int N;
		cin >> N;
		CLEAR(black);
		minC = INT_MAX;
		maxC = INT_MIN;
		minR = INT_MAX;
		maxR = INT_MIN;
		REP(row, N) {
			REP(column, N) {
				char ch;
				cin >> ch;
				if (ch == '.') {
					continue;
				}
				black[row][column] = true;
				MIN_UPDATE(minC, column);
				MAX_UPDATE(maxC, column);
				MIN_UPDATE(minR, row);
				MAX_UPDATE(maxR, row);
			}
		}

		printf("Case #%d: %s\n", testCase, solve() ? "YES" : "NO");
	}
}

35: Basketball Game

  • これまた面倒そう・・・
  • 選手の出し入れのところをいかに楽に書くかがポイントっぽい
  • C++の関数オブジェクト使えば楽に書けるかな?
  • Accepted
struct Student {
	string name;
	int shotPercentage;
	int height;
	int draftNumber;
	int playTime;
	int benchTime;

	Student() {
		shotPercentage = 0;
		height = 0;
		draftNumber = 0;
		playTime = 0;
		benchTime = 0;
	}

	bool operator == (const Student& rh) {
		return name == rh.name &&
			shotPercentage == rh.shotPercentage &&
			height == rh.height &&
			draftNumber == rh.draftNumber &&
			playTime == rh.playTime &&
			benchTime == rh.benchTime;
	}
};

bool compareByShotPercentageAndHeight(const Student& lh, const Student& rh) {
	return lh.shotPercentage != rh.shotPercentage ? lh.shotPercentage > rh.shotPercentage :
	lh.height > rh.height;
}

struct PlayTimeAndDraftNumberComparator : binary_function<Student, Student, bool> {
	bool operator()(const Student& lh, const Student& rh) {
		return lh.playTime != rh.playTime ? lh.playTime > rh.playTime :
		lh.draftNumber > rh.draftNumber;
	}
};

struct BenchTimeAndDraftNumberComparator : binary_function<Student, Student, bool> {
	bool operator()(const Student& lh, const Student& rh) {
		return lh.benchTime != rh.benchTime ? lh.benchTime > rh.benchTime :
		lh.draftNumber < rh.draftNumber;
	}
};

void play(int N, int M, int P, const vector<Student>& team, list<Student>& playing, list<Student>& bench) {
	REP(n, P) {
		playing.push_back(team[n]);
	}
	for (int n = P; n < team.size(); ++n){
		bench.push_back(team[n]);
	}

	REP(m, M) {
		for (auto& student : playing) {
			++student.playTime;
		}
		for (auto& student : bench) {
			++student.benchTime;
		}

		if (2 * P == N) {
			continue;
		}

		auto toBench = min_element(ALL(playing), PlayTimeAndDraftNumberComparator());
		auto toPlay = min_element(ALL(bench), BenchTimeAndDraftNumberComparator());
		playing.push_back(*toPlay);
		bench.push_back(*toBench);
		playing.remove(*toBench);
		bench.remove(*toPlay);
	}
}

int main() {
	std::ios::sync_with_stdio(false);

	int T;
	cin >> T;
	for (int testCase = 1; testCase <= T; ++testCase) {
		int N, M, P;
		cin >> N >> M >> P;

		vector<Student> students;
		REP(n, N) {
			Student s;
			cin >> s.name >> s.shotPercentage >> s.height;
			students.push_back(s);
		}

		sort(ALL(students), compareByShotPercentageAndHeight);

		vector<Student> teams[2];
		REP(n, N) {
			students[n].draftNumber = n + 1;
			teams[n & 1].push_back(students[n]);
		}


		list<Student> playing[2];
		list<Student> bench[2];

		play(N, M, P, teams[0], playing[0], bench[0]);
		play(N, M, P, teams[1], playing[1], bench[1]);

		vector<string> names;
		REP(team, 2) {
			for (const auto& student : playing[team]) {
				names.push_back(student.name);
			}
		}

		sort(ALL(names));

		printf("Case #%d:", testCase);
		for (const string& name : names) {
			printf(" %s", name.c_str());
		}
		printf("\n");
	}
}

45: Tennison

  • うげぇ・・・確率DPっぽいなにかorz
  • dp[自分が勝った数][相手が勝った数][晴れている確率の千分率] = (その状態になる確率) だとTLEするよなぁ
  • ・・・
  • よく考えたら[相手が勝った数]いらないじゃん
  • これなら確率DP苦手な自分でも解けそう
  • Accepted
int main() {
	std::ios::sync_with_stdio(false);

	int T;
	cin >> T;
	for (int testCase = 1; testCase <= T; ++testCase) {
		int K;
		double ps, pr, pi, pu, pw, pd, pl;
		cin >> K >> ps >> pr >> pi >> pu >> pw >> pd >> pl;
		int Ps, Pr, Pi, Pu, Pw, Pd, Pl;
		Ps = int(1000 * ps + 0.5);
		Pr = int(1000 * pr + 0.5);
		Pi = int(1000 * pi + 0.5);
		Pu = int(1000 * pu + 0.5);
		Pw = int(1000 * pw + 0.5);
		Pd = int(1000 * pd + 0.5);
		Pl = int(1000 * pl + 0.5);

		// [front/back][win count][prob for sunny]
		static double dp[2][128][1024];
		CLEAR(dp);
		int front = 0;
		int back = 1;
		dp[back][0][int(pi * 1000 + 0.5)] = 1.0;

		REP(k, K * 2) {
			memset(dp[front], 0, sizeof(double) * 128 * 1024);

			REP(prevWin, K) {
				if (k - prevWin >= K) {
					// Lose.
					continue;
				}

				REP(sunProb, 1000 + 1) {
					double current = dp[back][prevWin][sunProb];

					double winProb = sunProb / 1000.0 * ps + ((1000 - sunProb) / 1000.0 * pr);
					int nextSunProbUp = MIN(1000, sunProb + Pu);
					dp[front][prevWin + 1][nextSunProbUp] += current * winProb * pw;
					dp[front][prevWin + 1][sunProb] += current * winProb * (1.0 - pw);

					double loseProb = 1.0 - winProb;
					int nextSunProbDown = MAX(0, sunProb - Pd);
					dp[front][prevWin][nextSunProbDown] += current * loseProb * pl;
					dp[front][prevWin][sunProb] += current * loseProb * (1.0 - pl);
				}
			}

			// Process prevWin = K.
			REP(sunProb, 1000 + 1) {
				dp[front][K][sunProb] += dp[back][K][sunProb];
			}

			swap(front, back);
		}

		double answer = 0.0;
		REP(sunProb, 1000 + 1) {
			answer += dp[back][K][sunProb];
		}

		printf("Case #%d: %.6f\n", testCase, answer);
	}
}

Systen Test

ooo 439位 3問正解して予選通過しました。めでたしめでたし。

トラックバック - http://topcoder.g.hatena.ne.jp/nodchip/20131125
 |