Facebook Hacker Cup 2017 Round 1

奇跡的にミスらなくて, なんか全完した.

15. Beach Umbrellas

問題概要

${N(1 \le N \le 300)}$ 日の間, 以下の行動を繰り返す.

店に売られている ${M(1 \le M \le 300)}$ 個のパイのうちの何個かを買う. ${i}$ 日目の ${j}$ 番目のパイは ${C_{i,j}(1 \le C_{i,j} \le 1 000 000)}$ ドルである. また, このとき ${p}$ 個のパイを買ったとすると, ${p^2}$ ドルの税金が加わる.
夕食にパイを ${1}$ 個食べる. すなわち食べられるパイが存在しなければならない. このとき, 過去に買ったパイも食べることが可能.

上手くパイを買ったときの最小金額を求めよ.

テストケースの数 ${T \le 100}$ .

解法

夕食に食べられるパイが存在するかどうかは, 「何日目か」と「今までに買ったパイの個数」の情報があればよい. 遷移時に個数が日数を下回ったらダメ.

また, パイを買うときは安い順に買ったほうがいいので, ソートしておく.

この情報を持ってえいってやれば解ける. ここでえいっ＝メモ化再帰(？).

JOI とかにありそう. 古本屋 (Books) みたいな感じ？

遷移 ${O(M)}$ の状態数 ${O(N^2)}$ なので ${O(TN^2M)}$ .

ソース

#include<bits/stdc++.h>

using namespace std;

#define int long long
typedef long long int64;
const int64 INF = 1LL << 58;

int N, M, C[305][305];
int64 dp[305][305];

int64 rec(int day, int sum)
{
  if(day == N) return (0);
  if(~dp[day][sum]) return (dp[day][sum]);
  int64 add = 0, ret = INF;
  for(int i = 0; sum + i <= N && i <= M; i++) {
    add += C[day][i];
    if(sum + i < day + 1) continue;
    ret = min(ret, rec(day + 1, sum + i) + add + i * i);
  }
  return (dp[day][sum] = ret);
}


int64 Solution()
{
  cin >> N >> M;
  for(int i = 0; i < N; i++) {
    for(int j = 1; j <= M; j++) {
      cin >> C[i][j];
    }
    sort(C[i], C[i] + M + 1);
  }
  memset(dp, -1, sizeof(dp));
  return (rec(0, 0));
}

signed main()
{
  int T;
  cin >> T;
  for(int i = 1; i <= T; i++) {
    cout << "Case #" << i << ": " << Solution() << endl;
  }
}

25. Fighting the Zombies

問題概要

格子上に ${N(1 \le N \le 50)}$ 個の点が打たれていて, ${i}$ 番目の点は ${(X_i, Y_i) (1 \le X_i, Y_i \le 10^9)}$ である.

以下の操作を順に行う.

${Move(x, y, r, dx, dy)}$ : ${(x, y)}$ を中心とする半径 ${r}$ の円内に含まれる全ての点の ${X_i}$ , ${Y_i}$ それぞれに ${dx}$ , ${dy}$ を加える.
${Destroy(x, y)}$ : 左上 ${(x, y)}$ の辺長 ${R(1 \le R \le 10^9)}$ の正方形内の点を消す.

Move() と Destroy() を適切に呼び出した時, 消せる点の個数の最大値を求めよ.

テストケースの数 ${T \le 50}$ .

解法

わからなかったので悲しい解法を投げた.

円内に含ませる ${3}$ 点が決まれば, 円の中心座標や半径は一意に定まる. この ${3}$ 点を総当りし, 円の移動の変位, また正方形の左上の座標も入力で出てきた値で総当りする.

これに加えて, ${1}$ 点のみを移動する場合と, 一応 ${2}$ 点を直径にした円内の点を移動する場合を加えた.

なぜこれでいいのか正当性は分からないです！！

(勝手に引用)

@potetisensei 円周上に点が1~2個だけ乗る場合も調べたんですけどそれでも不十分ですか
— 滝本ひふみ (@MochaLatvia) 2017年1月16日

${O(TN^6)}$ . 30秒くらい待てば出力されるので勝ち(いいえ

ソース

#include<bits/stdc++.h>

using namespace std;

#define double long double
const double eps = 1e-10;
typedef long long int64;

#define SQR(x) ((x)*(x))

#define EQ0(x) ((-eps <= (x)) && ((x) <= eps))

// 直線の垂直二等分線算出
void CalcPerpLineSeg(double sx, double sy, double ex, double ey, double &a, double &b)
{
  double a1 = (sy - ey) / (sx - ex);
  if(EQ0(a1)) a = 1.0;
  else a = -1.0 / a1;
  double cx(sx + (ex - sx) / 2.0);
  double cy(sy + (ey - sy) / 2.0);
  if(EQ0(a1)) b = 0;
  else b = cy - a * cx;
}

bool CircleBy3Point(double x1, double y1, double x2, double y2, double x3, double y3,
                    double &cx, double &cy, double &dRad)
{
  double a, b, c, d;
  CalcPerpLineSeg(x1, y1, x2, y2, a, b);
  CalcPerpLineSeg(x2, y2, x3, y3, c, d);
  if(EQ0(a - c)) return false;
  cx = (d - b) / (a - c);
  cy = a * cx + b;
  dRad = SQR(cx - x1) + SQR(cy - y1);
  return true;
}

int64 Solution()
{
  int N, X[50], Y[50], R;
  cin >> N >> R;

  int64 ret = 0;
  for(int i = 0; i < N; i++) {
    cin >> X[i] >> Y[i];
  }

  for(int i = 0; i < N; i++) {
    for(int j = i; j < N; j++) {
      double medX = (X[i] + X[j]) * 0.5;
      double medY = (Y[i] + Y[j]) * 0.5;
      double radius = SQR(medX - X[i]) + SQR(medY - Y[i]);
      vector< int > inner, other;
      for(int k = 0; k < N; k++) {
        if(SQR(medX - X[k]) + SQR(medY - Y[k]) < radius + eps) {
          inner.push_back(k);
        } else {
          other.push_back(k);
        }
      }

      int64 res1 = 0, res2 = 0;
      for(auto &s : other) {
        for(auto &t : other) {
          int64 proc = 0;
          int64 sx = X[s], sy = Y[t];
          int64 gx = sx + R, gy = sy + R;
          for(auto &k : other) {
            if(sx <= X[k] && X[k] <= gx && sy <= Y[k] && Y[k] <= gy) ++proc;
          }
          res1 = max(res1, proc);
        }
      }
      for(auto &s : inner) {
        for(auto &t : inner) {
          int64 proc = 0;
          int64 sx = X[s], sy = Y[t];
          int64 gx = sx + R, gy = sy + R;
          for(auto &k : inner) {
            if(sx <= X[k] && X[k] <= gx && sy <= Y[k] && Y[k] <= gy) ++proc;
          }
          res2 = max(res2, proc);
        }
      }
      ret = max(ret, res1 + res2);
    }
  }

  for(int i = 0; i < N; i++) {
    for(int j = i + 1; j < N; j++) {
      for(int z = j + 1; z < N; z++) {

        double medX, medY, radius;
        if(!CircleBy3Point(X[i], Y[i], X[j], Y[j], X[z], Y[z], medX, medY, radius)) continue;
        vector< int > inner, other;
        for(int k = 0; k < N; k++) {
          if(SQR(medX - X[k]) + SQR(medY - Y[k]) < radius + eps) {
            inner.push_back(k);
          } else {
            other.push_back(k);
          }
        }

        int64 res1 = 0, res2 = 0;
        for(auto &s : other) {
          for(auto &t : other) {
            int64 proc = 0;
            int64 sx = X[s], sy = Y[t];
            int64 gx = sx + R, gy = sy + R;
            for(auto &k : other) {
              if(sx <= X[k] && X[k] <= gx && sy <= Y[k] && Y[k] <= gy) ++proc;
            }
            res1 = max(res1, proc);
          }
        }
        for(auto &s : inner) {
          for(auto &t : inner) {
            int64 proc = 0;
            int64 sx = X[s], sy = Y[t];
            int64 gx = sx + R, gy = sy + R;
            for(auto &k : inner) {
              if(sx <= X[k] && X[k] <= gx && sy <= Y[k] && Y[k] <= gy) ++proc;
            }
            res2 = max(res2, proc);
          }
        }
        ret = max(ret, res1 + res2);
      }
    }
  }
  return (ret);
}

signed main()
{
  int T;
  cin >> T;
  for(int i = 1; i <= T; i++) {
    cout << "Case #" << i << ": " << Solution() << endl;
  }
}

25. Manic Moving

問題概要

${N(1 \le N \le 100)}$ 頂点 ${M(1 \le M \le 5000)}$ 個の重みつき無向辺からなるグラフが与えられる. 最初トラックは頂点 ${1}$ にある.

${K(1 \le K \le 5000)}$ 個の家族があって, ${i}$ 番目の家族は ${S_i}$ から ${T_i}$ に引越すので, これらの荷物を運びたい.

但し, トラックには最大 ${2}$ 家族分の荷物しか同時に持つことが出来ない. また, ${i}$ 番目の家族の荷物を積む前に ${j(j \gt i)}$ 番目の家族の荷物を積むことは不可能で, ${i}$ 番目の家族の荷物をおろす前に ${j(j \gt i)}$ 番目の家族の荷物をおろすことは不可能.

全ての家族の引っ越しを処理するとき, トラックの走行する辺の重みの和の最小値を求めよ.

テストケースの数 ${T \le 100}$ .

解法

まず任意の街間を移動するとき最小コストで移動したいので事前にWFして求めておく.

遷移を列挙すると ${4}$ 通りくらいしかないので DP. 具体的な遷移はソースに書いてあるので(面倒なだけ

${O(T(N^3+K))}$ .

ソース

#include<bits/stdc++.h>

using namespace std;

#define int long long
const int INF = 1LL << 50;

int N, M, K, g[105][105];
int s[5005], d[5005];
map< int, int > dp[5005][2];

int rec(int idx, int prevCity, bool flag)
{
  if(idx == K) return (flag ? INF : 0);
  if(dp[idx][flag].count(prevCity)) return (dp[idx][flag][prevCity]);

  int ret = INF;
  if(flag) { // 前の荷物を持っている

    // 自分の荷物を持つ -> 前の荷物を届ける -> ?
    int InitialCost = g[prevCity][s[idx]] + g[s[idx]][d[idx - 1]];

    // -> 自分の荷物を届ける
    ret = min(ret, rec(idx + 1, d[idx], 0) + g[d[idx - 1]][d[idx]] + InitialCost);

    // -> 自分の荷物は持ったまま
    ret = min(ret, rec(idx + 1, d[idx - 1], 1) + InitialCost);

  } else { // 前の荷物は持っていない

    // 自分の荷物を持つ
    int InitialCost = g[prevCity][s[idx]];

    // -> 自分の荷物を届ける
    ret = min(ret, rec(idx + 1, d[idx], 0) + g[s[idx]][d[idx]] + InitialCost);

    // -> 自分の荷物は持ったまま
    ret = min(ret, rec(idx + 1, s[idx], 1) + InitialCost);

  }
  return (dp[idx][flag][prevCity] = ret);
}

int Solution()
{
  fill_n(*g, 105 * 105, INF);
  for(int i = 0; i < 105; i++) g[i][i] = 0;
  for(int i = 0; i < 5005; i++) dp[i][0].clear(), dp[i][1].clear();

  cin >> N >> M >> K;
  for(int i = 0; i < M; i++) {
    int A, B, G;
    cin >> A >> B >> G;
    --A, --B;
    g[A][B] = min(g[A][B], G);
    g[B][A] = min(g[B][A], G);
  }
  for(int i = 0; i < K; i++) {
    cin >> s[i] >> d[i];
    --s[i], --d[i];
  }

  for(int k = 0; k < N; k++) {
    for(int i = 0; i < N; i++) {
      for(int j = 0; j < N; j++) {
        g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
      }
    }
  }

  int curr = min(rec(1, s[0], 1) + g[0][s[0]], rec(1, d[0], 0) + g[0][s[0]] + g[s[0]][d[0]]);
  if(curr >= INF) return(-1);
  else return(curr);
}

signed main()
{
  int T;
  cin >> T;
  for(int i = 1; i <= T; i++) {
    cout << "Case #" << i << ": " << Solution() << endl;
  }
}

40. Beach Umbrellas

問題概要

${n(1 \le n \le 2000)}$ 個のグループがあって, グループ ${i}$ は半径 ${R_i(1 \le R_i \le 2000)}$ の傘を持っている.

また ${m(1 \le m \le 10^9)}$ 個の傘を指せるポイントが距離 ${1}$ の等間隔で並んでいる.

傘同士が被らない条件を満たすように傘を置く時, 置き方の個数を ${10^9+7}$ で割った余りで求めよ.

解法

${n = 1}$ のとき ${m}$ 通り.

${n \ge 2}$ のときを考える. ここで ${S = 2\sum_{k=1}^{n} {R_k}}$ とする.

もう少し条件を厳しくして, 傘が長さ ${m}$ の区間からはみ出してはいけないという条件をつけると, この解は単純な二項係数となる. たぶん ${ {}_{m+n-S} \mathrm{C} _{n} n!}$ .(嘘かも)

はみ出すのは左端の傘か右端の傘のみであることに着目する. この傘について傘の中心から外側に出る分には他と干渉しないことを考えると, 半径として扱っても問題ないことがわかる.

従って解は, (左端の傘 ${i}$ , 右端の傘 ${j(i \ne j)}$ ) を総当りして, すべて足し合わせる. ${i \lt j}$ としてもよい(最後に答えを ${2}$ 倍すればOK).

(左端の傘 ${i}$ , 右端の傘 ${j}$ ) のときの組み合わせの個数は, ${{}_{m + n - 1 - S + R_i + R_j} \mathrm{C} _n (n-2)!}$ .

ここで愚直にこの値を求めているとたぶんダメなので高速化する. ${(n-2)!}$ は全体に掛かるので最後に掛ければ良い. 次に着目するのは ${{}_{m + n - 1 - S + R_i + R_j} \mathrm{C} _n}$ で ${n}$ は定数であることである.

左側の部分の値を列挙してソートして, 小さい順に求めていけば ${{}_{n} \mathrm{C} _k = {}_{n-1} \mathrm{C} _k \times n / (n-k) }$ なので前の計算結果を生かして計算量を削減することができる. （→→→↓↓...↓みたいな感じ(通じろ))

計算量は ${O(T(N^2 + max(R_i)) \log N^2)}$ みたいな感じ.

ソース

好き。

#include<bits/stdc++.h>

using namespace std;

#define int long long
typedef long long int64;
const int mod = 1e9 + 7;

int64 modPow(int64 x, int64 n)
{
  if(n == 0) return (1);
  int64 ret = modPow(x, n / 2);
  (ret *= ret) %= mod;
  if(n & 1) (ret *= x) %= mod;
  return (ret);
}

int64 modInv(int64 a)
{
  return (modPow(a, mod - 2));
}

int64 combination(vector< int64 > &ns, int k)
{
  if(ns.empty()) return (0);
  int64 now = 1, ret = 0;
  for(int i = 1; i <= k; i++) {
    now *= (ns.front() - i + 1) % mod;
    now %= mod;
    now *= modInv(i);
    now %= mod;
  }
  (ret += now) %= mod;

  int64 reach = ns.front();
  for(int i = 1; i < ns.size(); i++) {
    // Combination[n,k] で k が固定
    // Combination[n,k]=Combination[n-1,k]*n/(n-k) らしい
    while(reach < ns[i]) {
      ++reach;
      (now *= reach) %= mod;
      (now *= modInv(reach - k)) %= mod;
    }
    (ret += now) %= mod;
  }
  return (ret);
}


int Solution()
{
  int N, M, R[2000];
  cin >> N >> M;

  int64 all = M + N - 1;
  for(int i = 0; i < N; i++) {
    cin >> R[i];
    all -= R[i] * 2;
  }
  if(N == 1) return (M % mod);

  int64 ret = 0;
  vector< int64 > calc;
  for(int i = 0; i < N; i++) {
    int64 vv = all + R[i];
    for(int j = i + 1; j < N; j++) {
      int64 xx = vv + R[j];
      if(xx >= N) calc.push_back(xx);
    }
  }
  sort(begin(calc), end(calc));
  int64 fact = 1;
  for(int i = 1; i <= N - 2; i++) (fact *= i) %= mod;
  return (1LL * combination(calc, N) * 2 % mod * fact % mod);
}

signed main()
{
  int T;
  cin >> T;
  for(int i = 1; i <= T; i++) {
    cout << "Case #" << i << ": " << Solution() << endl;
  }
}

ei1333の日記

ぺこい

Facebook Hacker Cup 2017 Round 1

15. Beach Umbrellas

問題概要

解法

ソース

25. Fighting the Zombies

問題概要

解法

ソース

25. Manic Moving

問題概要

解法

ソース

40. Beach Umbrellas

問題概要

解法

ソース