読者です 読者をやめる 読者になる 読者になる

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