Facebook Hacker Cup 2016 Round 1 15-25
15 Coding Contest Creation
DP
コード
#define _GLIBCXX_DEBUG #include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iomanip> #include <algorithm> #include <cmath> #include <string> #include <vector> #include <list> #include <queue> #include <stack> #include <set> #include <map> #include <bitset> #include <numeric> #include <limits> #include <climits> #include <cfloat> #include <functional> #include <string.h> using namespace std; typedef signed long long ll; #define ALL(a) a.begin(), a.end() #define UNIQUE(a) a.erase(unique(a.begin(), a.end()), a.end()) bool ok(const int &a, const int &b) { return a < b && b - a <= 10; } bool okl_l(const int &a, const int &c) { return a + 1 < c && c <= a + 20; } bool ok4(const int &a, const int &b, const int &c, const int &d) { return ok(a, b) && ok(b, c) && ok(c, d); } bool ok3(const int &a, const int &b, const int &c) { if (ok(a, b) && ok(b, c)) return true; // abco if (ok(a, b) && okl_l(b, c)) return true; // aboc if (okl_l(a, b) && ok(b, c)) return true; // aobc return false; } bool ok2(const int &a, const int &b) { if (ok(a, b)) return true; // aboo if (okl_l(a, b)) return true; // aobo if (a + 3 <= b && b <= a + 30) return true; // aoob return false; } int solve(const vector<int> &D) { int N = D.size(); vector<int> dp(N + 1, N * 4); dp[0] = 0; for (int i = 0; i < N; ++i) { if (i + 3 < N && ok4(D[i], D[i + 1], D[i + 2], D[i + 3])) { dp[i + 4] = min(dp[i + 4], dp[i]); } if (i + 2 < N && ok3(D[i], D[i + 1], D[i + 2])) { dp[i + 3] = min(dp[i + 3], dp[i] + 1); } if (i + 1 < N && ok2(D[i], D[i + 1])) { dp[i + 2] = min(dp[i + 2], dp[i] + 2); } dp[i + 1] = min(dp[i + 1], dp[i] + 3); } return dp[N]; } int main() { cin.tie(0); ios::sync_with_stdio(false); std::random_device rnd; std::mt19937 mt(rnd()); int T; cin >> T; // T = 50; for (int i = 0; i < T; ++i) { int N; cin >> N; vector<int> D(N); for (int i = 0; i < N; ++i) { cin >> D[i]; } int c = solve(D); cout << "Case #"; cout << (i + 1); cout << ": "; cout << c << endl; } }
20 Laundro, Matt
二分探索で洗濯が全て終わる時刻を出し、乾燥はその時刻に合わせて愚直にシミュレーション。
コード
#include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iomanip> #include <algorithm> #include <cmath> #include <string> #include <vector> #include <list> #include <queue> #include <stack> #include <set> #include <map> #include <bitset> #include <numeric> #include <limits> #include <climits> #include <cfloat> #include <functional> #include <string.h> using namespace std; typedef signed long long ll; #define UNIQUE(a) a.erase(unique(a.begin(), a.end()), a.end()) bool ok(int L, const vector<ll> &W, ll T) { ll cnt = 0; int N = W.size(); for (int i = 0; i < N; ++i) { cnt += T / W[i]; } if (cnt < L) return false; return true; } ll solve(int L, int M, int D, const vector<ll> &W) { ll high = 1000000000000000000; ll low = 0; while (high > low + 1) { ll T = (high + low) / 2; if (ok(L, W, T)) { high = T; } else { low = T; } } for (int i = 1; i <= 10; ++i) { if (!ok(L, W, high - i)) { high = high - i + 1; break; } } cerr << high << endl; vector<ll> matt; ll T = high; int N = W.size(); for (int i = 0; i < N; ++i) { for (ll j = 1; j * W[i] <= T; ++j) { matt.push_back(W[i] * j); } } sort(matt.begin(), matt.end()); cerr << matt.size() << endl; deque<ll> que; for (int i = 0; i < M; ++i) { que.push_back(0); } ll ans = 0; for (int i = 0; i < L; ++i) { ll d = que.front(); d = max(d + D, matt[i] + D); que.pop_front(); que.push_back(d); ans = max(ans, d); } return ans; } int main() { cin.tie(0); ios::sync_with_stdio(false); std::random_device rnd; std::mt19937 mt(rnd()); int T; cin >> T; // T = 1; for (int i = 0; i < T; ++i) { int L, N, M, D; cin >> L >> N >> M >> D; // L = mt() % 1000000 + 1; // N = mt() % 100000 + 1; // int b = 100000; // M = mt() % b + 1; // D = mt() % b + 1; cerr << L << " " << N << " " << M << " " << D << endl; vector<ll> W(N); for (int i = 0; i < N; ++i) { cin >> W[i]; // W[i] = mt() % 1000000000 + 1; } if (i + 1 <= 28) continue; sort(W.begin(), W.end()); ll c = solve(L, M, D, W); cout << "Case #"; cout << (i + 1); cout << ": "; cout << c << endl; } }
25 Yachtzee
愚直に求める。
コード
#define _GLIBCXX_DEBUG #include <cstdio> #include <iostream> #include <sstream> #include <fstream> #include <iomanip> #include <algorithm> #include <cmath> #include <string> #include <vector> #include <list> #include <queue> #include <stack> #include <set> #include <map> #include <bitset> #include <numeric> #include <limits> #include <climits> #include <cfloat> #include <functional> #include <string.h> using namespace std; typedef signed long long ll; #define UNIQUE(a) a.erase(unique(a.begin(), a.end()), a.end()) ll calc(ll a, const vector<ll> &C, const vector<ll> &accC) { int N = C.size(); ll all = 0; for (int i = 0; i < N; ++i) { // all += (C[i] - 1) * (C[i]) / 2; all += C[i] * C[i]; } ll cnt = 0; ll turn = a / accC[N - 1]; cnt += turn * all; a %= accC[N - 1]; for (int i = 0; i < N; ++i) { ll now = min(a, C[i]); cnt += now * now; a -= C[i]; if (a <= 0) break; } return cnt; } double solve(const int A, const int B, const vector<ll> &C) { int N = C.size(); vector<ll> accC(C); for (int i = 1; i < N; ++i) accC[i] += accC[i - 1]; ll calca = calc(A, C, accC); ll calcb = calc(B, C, accC); cerr << calca << endl; cerr << calcb << endl; double ans = calcb - calca; return ans / (B - A) / 2; } int main() { cin.tie(0); ios::sync_with_stdio(false); std::random_device rnd; std::mt19937 mt(rnd()); int T; cin >> T; for (int i = 0; i < T; ++i) { int N, A, B; cin >> N >> A >> B; vector<ll> C(N); for (int i = 0; i < N; ++i) { cin >> C[i]; } double c = solve(A, B, C); // cout << "Case #"; // cout << (i + 1); // cout << ": "; // cout << c << endl; printf("Case #%d: %.13lf\n", (i + 1), c); } }
