Facebook Hacker Cup 2016 Round 1

学校の課題とレポートと疲労と無気力などが被ってしまって時間がとれなかったけど2完でRound2へ。

15: Coding Contest Creation

https://www.facebook.com/hackercup/problem/798506286925018/

問題概要

N個の問題があり、それぞれの問題には難易度 Wi が定められている。
この問題を先頭から4つずつ取り出して、順にコンテストに出題する。すべての問題を出題しなければならない。ただし、4つの問題の難易度は狭義単調増加で、隣接する問題の難易度の差は10以下である必要がある。
これを満たすように新しい問題を問題列の任意の位置に追加するとき、新しい問題の最小値を求めよ。

解法

Grundy。O(N)。Grundyこわい。DPしてやろうかなぁって思ったけどそこまで非自明じゃない気がしたので、Grundyしたら通った。このコンテストに対して、この条件が満たされているのか気になった。

先頭から順に4つずつ取り出して、コンテストの出題条件を満たしているかどうか、問題の定義通りに見る。満たしているならそのまま出題すればよくて、満たしてなければ、(前の問題の難易度 + 10) の難易度の問題を追加する。

もうちょっと詳しく・・・。満たしていない場合に考えられるのは以下の2通り。

• 前の難易度 ≥ 次の難易度
• 次の難易度 - 前の難易度 > 10

両方において (前の難易度 + 10) の難易度を追加することを考える。前者は4問出題し終わるまで繰り返すことになって、後者には、次の難易度に対してなるべく近い難易度になるように追加しているので、まぁ成り立つ。

ソース

#include<bits/stdc++.h>
using namespace std;
const int INF = 1 << 30;

int Solve()
{
  int N, D[100001];

  cin >> N;
  for(int i = 0; i < N; i++) {
    cin >> D[i];
  }
  D[N] = INF;
  
  int ret = 0, ptr = 0;
  while(ptr < N) {
    int now = D[ptr++];
    for(int i = 1; i < 4; i++) {
      if(now < D[ptr] && D[ptr] - now <= 10) {
        now = D[ptr++];
      } else {
        now += 10;
        ++ret;
      }
    }
  }
  return(ret);
}

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

20: Laundro, Matt

https://www.facebook.com/hackercup/problem/1611251319125133/

問題概要

L個の洗濯物をコインランドリーで洗って乾かす。コインランドリーには、N個の洗濯機とM個の乾燥機がある。
それぞれの洗濯機は 洗濯物を 1 個洗うのに Wi 分かかる。洗い終わった洗濯物は待機場所にストックできる。乾燥機は、すべての乾燥機において ストックされた洗濯物を 1 個乾かすのに D 分かかる。洗濯機や乾燥機について、複数の洗濯物を同じ機械に入れてで同時に洗濯や乾燥はできない。
すべての洗濯物を洗って乾かすまでにかかる最短の所要時間を求めよ。

解法

L が 10^6, N が 10^5 となかなか大きい。log がつきそう。

まず、すべての洗濯物を洗い終えるまでの最短時間は二分探索すれば求まる。x 分以内に L 個洗えるかどうかという問題を解けばよくて、これはそれぞれの洗濯機に対し x 分で洗える洗濯物の数(x / Wi 個)を求め足せばわかる。O(N log N)。

で、ここからが成り立つか不安。洗濯物を洗い終える最短時間が、乾燥機を含めても最短時間になるのか怪しかった。まあ、わざわざ各々の洗濯物を洗い終える時間を遅らせる必要はなさそうなので、これは成立するように思える。

よって、洗濯物を洗い終える最短時間で洗濯物を洗ったとき、それぞれの洗濯物について洗い終える時間を求めておく。O(L)。←ここら辺日本語に疎い
あとは、早く仕上がる洗濯物から順にGrundyに最短で乾燥機に入れていく。具体的には、乾燥機が空いていればDirectに入れて、空いてなければ1つの他の荷物の乾燥が終わる最短時間を待って入れる。O(L log L)。

適当な考察なので、定数倍落とせる気がする。

ソース

#include<bits/stdc++.h>
using namespace std;
typedef long long int64;
typedef pair< int64, int64 > Pi;

int64 Solve()
{
  int64 L, N, M, D, W[100000];
  cin >> L >> N >> M >> D;
  for(int i = 0; i < N; i++) {
    cin >> W[i];
  }

  int64 low = 0, high = 1LL << 58;
  while(high - low > 0) {
    int64 mid = (low + high) >> 1LL;
    int64 sum = 0;
    for(int i = 0; i < N; i++) {
      sum += mid / W[i];
    }
    if(sum >= L) high = mid;
    else low = mid + 1;
  }

  vector< int64 > times;
  for(int i = 0; i < N; i++) {
    for(int64 j = W[i]; j <= low; j += W[i]) {
      times.push_back(j);
    }
  }
  sort(times.begin(), times.end());

  priority_queue< int64, vector< int64 >, greater< int64 > > Flush;
  int64 ret = 0;

  for(int i = 0; i < L; i++) {
    if(Flush.size() < M) {
      Flush.push(times[i] + D);
      ret = max(ret, times[i] + D);
    } else {
      int64 Head = Flush.top(); Flush.pop();
      Flush.push(max(Head, times[i]) + D);
      ret = max(ret, max(Head, times[i]) + D);
    }
  }
  return(ret);
}

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