naoya_t@hatenablog

いわゆるチラシノウラであります

Facebook Hacker Cup 2016 : Round 1

Qiitaにはいくつか記事を書いていますがはてなでは1年以上ぶりです。
普段はPythonばかり書いています。最近はtheanoが気に入っています。あとclickと。

かよちん生誕祭に開催されたFacebook Hacker CupのR1でなぜか全完できたので、たまには記事を書こうという気になりました。
f:id:n4_t:20160118074840p:plain

Round 1 : 1/17 3am JST〜1/18 3am JST(24時間)

Facebook Hacker Cup 2016 Round 1

全部で4問 (15,20,25,40)。30点以上獲得すれば通過。
D以外だと2問取らないと30点にならないように出来てる。これはハードかも。

D. Boomerang Tournament (40 points)

夜中に起きたら始まってたので、とりあえず問題を4つとも読んでからお風呂でリラックス。
最後に読んだDを考え始めてて、途中まで実装して、あとはビットマスクでごにょごにょすれば行ける!とか思いながら寝落ち。

2人ずつ (nC2)、4人ずつ (nC4)、のグループで、(その中で組まれた任意のトーナメント対戦で)勝つ可能性が1つでもある者・負ける可能性が1つもない者をそれぞれ決勝まで(メモ化なりDPなりで)bitで持ち上がれば計算量は減らせそう。(bitDPか)
起き上がって実装を仕上げて、大きなテストケースでも時間に余裕があるのを確認して、brute forceな(N=8までしか行けない)コードの解と照合して、提出。

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <vector>
#include <map>
#include <set>

using namespace std;
#define all(c)  (c).begin(),(c).end()
#define tr(i,c)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)

int N, K, P;
vector<vector<int> > W;
vector<int> top, bottom;
vector<int> mm_top, mm_bottom;
vector<vector<set<int> > > pset;

vector<int> winnable, losable;

void sub(int k) {
  tr(it, pset[K][1<<k]) {
    int pat = *it;
    mm_top[pat] = 0;
    mm_bottom[pat] = pat;

    if (k == 0) {
      mm_top[pat] = mm_bottom[pat] = pat;
      continue;
    }

    tr(it2, pset[K][1<<(k-1)]) {
      int mask0 = *it2;
      if ((pat & mask0) != mask0) continue;
      int mask1 = pat - mask0;
      if (mask0 > mask1) continue;

      int t0 = mm_top[mask0], t1 = mm_top[mask1];
      int t0_ = 0, t1_ = 0;
      int b0 = mm_bottom[mask0], b1 = mm_bottom[mask1]; // ここまで負けられない
      int b0_ = b0, b1_ = b1;

      for (int i=0,m=1; i<N; ++i, m<<=1) {
        if (m & t0) {
          if (winnable[i] & t1) {
            t0_ |= m;
            top[i] = k;
          }
        } else if (m & t1) {
          if (winnable[i] & t0) {
            t1_ |= m;
            top[i] = k;
          }
        }

        if (m & b0) {
          if (losable[i] & b1) {
            b0_ &= ~m;
            bottom[i] = min(bottom[i], k);
          }
        } else if (m & b1) {
          if (losable[i] & b0) {
            b1_ &= ~m;
            bottom[i] = min(bottom[i], k);
          }
        }
      }

      int t = t0_ | t1_;
      int b = b0_ | b1_;

      mm_top[pat] |= t;
      mm_bottom[pat] &= b;
    }
  }
}

int main() {
  map<int,int> _log2;
  _log2[1] = 0;
  _log2[2] = 1;
  _log2[4] = 2;
  _log2[8] = 3;
  _log2[16] = 4;

  int _rank[] = { 1, 2, 3, 5, 9 };
  int _2k[] = { 1, 2, 4, 8, 16 }; // 2^k
  int _22k[] = { 1, 4, 16, 256, 65536 }; // 2^(2^k)

  pset.resize(5);

  for (int k=0; k<=4; ++k) {
    pset[k].resize(1+_2k[k]);
  }
  for (int p=1; p<65536; ++p) {
    int pc = __builtin_popcount(p);
    if (__builtin_popcount(pc) != 1) continue;

    switch (pc) {
    case 1:
      if (p < _22k[0])
        pset[0][pc].insert(p);
      // fall thru
    case 2:
      if (p < _22k[1])
        pset[1][pc].insert(p);
      // fall thru
    case 4:
      if (p < _22k[2])
        pset[2][pc].insert(p);
      // fall thru
    case 8:
      if (p < _22k[3])
        pset[3][pc].insert(p);
      // fall thru
    case 16:
      if (p < _22k[4])
        pset[4][pc].insert(p);
      break;
    }
  }

  int _T; cin >> _T;
  rep(_t,_T){
    cin >> N;
    K = _log2[N];
    W.assign(N, vector<int>(N));
    rep(i,N) rep(j,N) cin >> W[i][j];
    P = 1 << N;

    mm_top.assign(P, -1);
    mm_bottom.assign(P, -1);

    top.assign(N, 0);
    bottom.assign(N, K+1);

    winnable.resize(N);
    losable.resize(N);
    rep(i,N) {
      int x = 0;
      for (int j=0,m=1; j<N; ++j,m<<=1) {
        if (W[i][j]) x |= m;
      }
      int y = (1 << N) - 1 - x;
      winnable[i] = x;
      losable[i] = y;
    }

    for (int k=0; k<=K; ++k) sub(k);

    printf("Case #%d: \n", 1+_t);
    rep(i, N) {
      int t = _rank[K - top[i]];
      int b = _rank[K - (bottom[i] - 1)];
      printf("%d %d\n", t, b);
    }
  }
}

(おまけ)検算に使った乱暴なシミュレーション。next_permutation() で回してるのでN=8が限界。

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

int main(){
  map<int,int> _log2;
  _log2[1] = 0;
  _log2[2] = 1;
  _log2[4] = 2;
  _log2[8] = 3;
  _log2[16] = 4;
  int _rank[] = { 1, 2, 3, 5, 9 };

  int N, K;
  vector<vector<int> > W;

  int _T; cin>>_T;
  rep(_t,_T){
    cin >> N;
    K = _log2[N];
    W.assign(N, vector<int>(N));
    rep(i,N) rep(j,N) cin >> W[i][j];

    vector<int> iota(N);
    rep(i,N) iota[i] = i;

    vector<int> lo(N, K+1), hi(N, -1);
    do {
      int skip = N/2;
      vector<int> z(all(iota)), r(N, 0);
      for (int l=0,skip=1; skip<N; ++l,skip*=2) {
        for (int i=0; i<N; i+=skip*2) {
          int a = z[i], b = z[i+skip];
          if (!W[a][b]) z[i] = b;
          ++r[ z[i] ];
        }
      }
      rep(i,N) {
        lo[i] = min(lo[i], r[i]);
        hi[i] = max(hi[i], r[i]);
      }
    } while (next_permutation(all(iota)));

    printf("Case #%d: \n", 1+_t);
    rep(i,N) {
      printf("%d %d\n", _rank[K - hi[i]], _rank[K - lo[i]]);
    }
  }
}

C. Yachtzee (25 points)

続いてC。
積分(というか三角形の面積を足しあわせていったもの)して底辺で割ればいいだけだよね。
これは一番簡単な気がする。
a〜bの積分は、(0〜b) - (0〜a) にした方が分かりやすい。
あとは精度と、時間が間に合うかというところだけ。
面積計算は、2倍にして整数 (long long) で計算すればいいかなと。最後の割り算だけdoubleで。

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long ll;
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define rep(var,n)  for(int var=0;var<(n);var++)

int N;
vector<ll> C, Cacc;
vector<ll> S2; // S*2
ll W;

ll f(ll x) {
  ll q = x / W, r = x % W;

  vector<ll>::iterator it = upper_bound(all(Cacc), r);
  int ix = (it - Cacc.begin()) - 1;

  ll d = r - Cacc[ix];
  ll s = S2[ix] + d*d;

  return S2[N] * q + s;
}

int main(){
  int _T; cin>>_T;
  rep(_t,_T){
    cin >> N;
    ll a, b; cin >> a >> b;

    C.resize(N); Cacc.resize(N+1); S2.resize(N+1);
    Cacc[0] = S2[0] = 0LL;
    rep(i,N) {
      ll c; cin >> c;
      C[i] = c;
      Cacc[i+1] = Cacc[i] + c;
      S2[i+1] = S2[i] + c*c;
    }
    W = Cacc[N];

    ll aq = a / W, ar = a % W;
    ll bq = b / W, br = b % W;

    ll ofs = W * aq;
    ll s2 = f(b-ofs) - f(a-ofs); // f(b) - f(a)

    double ans = 0.5*s2 / (b-a);
    printf("Case #%d: %.9f\n", 1+_t, ans);
  }
}

B. Laundro, Matt (20 points)

Bを考えてて、洗濯フェーズの所要時間の最小化は二分探索でできるなあと思ったんだけど
その後の乾燥フェーズに投げるにあたって、洗濯フェーズだけで所要時間最小化したパターンが
乾燥も含めて最短になるのか自信がなくて、後回し(というか寝落ち)。

最小所要時間から、個々の洗濯機の最大稼働回数を求めて、priority queueに次に洗濯機が空く時刻を投入して行って、L個の洗濯物の1つ1つができるだけ早いタイミングで終わるパターンを得て*1キューに入れ、
乾燥フェーズのシミュレーション。こちらもpriority queueにM台*2の乾燥機の空くタイミングを投入。

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
#define all(c)  (c).begin(),(c).end()
#define rep(var,n)  for(int var=0;var<(n);var++)

ll L, N, M, D;
vector<ll> W;

bool p(ll a) {
  ll qs = 0;
  rep(i, N) qs += a / W[i];
  return qs >= L;
}

int main(){
  int _T; cin>>_T;
  rep(_t,_T){
    cin >> L >> N >> M >> D;
    M = min(M, L); // 乾燥機は1e9個も要らんだろ
    W.resize(N); rep(i,N) cin >> W[i];
    sort(all(W));

    // 洗濯側の最短所要時間 a を binary search で
    ll lo = 0, hi = W[N-1]*L, a = hi;
    // assert p(lo) == false
    // assert p(hi) == true
    do {
      ll mi = (lo + hi) / 2; // 1e15 < 2^50 < LONG_LONG_MAX
      if (p(mi)) {
        a = hi = mi;
      } else {
        lo = mi;
      }
    } while (hi > lo+1);

    // 所要時間を a として、なるはやで仕上がる順に洗濯機に投入したい
    // q は洗濯仕上がり時刻のリスト
    priority_queue<ll, vector<ll>, greater<ll> > pq;
    rep(i,N) {
      ll wi = W[i];
      for (ll w=wi; w<=a; w+=wi) {
        pq.push(w);
      }
    }
    vector<ll> q;
    rep(i, L) {
      q.push_back( pq.top() ); pq.pop();
    }
    while (!pq.empty()) pq.pop();

    // 乾燥機が使える時刻。普通のqueueでいいのかも
    priority_queue<ll, vector<ll>, greater<ll> > pq2;
    rep(i, M) pq2.push(0);

    ll ans;

    rep(i, L) {
      ll t = q[i];
      ll d = pq2.top(); pq2.pop(); // first available dryer
      ll next = max(d, t);
      pq2.push(next + D);
      if (i == L-1) ans = next + D;
    }
    while (!pq2.empty()) pq2.pop();

    printf("Case #%d: %lld\n", 1+_t, ans);
  }
}

A. Coding Contest Creation (15 points)

(寝落ち後に)Bを後回しにしてAから。
greedyに取っていけば行けるような気もするんだけど、ミスなく書ける気がしないんだよな…
ちょっと出かけようと思って、歩いてたら頭の中でDPの表が書けたので、そのまま実装して提出。
問目が4つ組の何番目かの表を作って編集距離みたいにDP。

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <vector>

using namespace std;
#define all(c)  (c).begin(),(c).end()
#define rep(var,n)  for(int var=0;var<(n);var++)

inline int min4(int a, int b, int c, int d) { return min(min(a,b),min(c,d)); }

int main(){
  int _T; cin>>_T;
  rep(_t,_T){
    int N; cin >> N; // 1-100000
    vector<int> D(N); // 1-100
    rep(i,N) cin >> D[i];

    vector<vector<int> > dp(N, vector<int>(4)); // dp[i][n], n=0,1,2,3は4つ組の何番目か, 値は編集距離
    dp[0][0] = 0; dp[0][1] = 1; dp[0][2] = 2; dp[0][3] = 3;
    // D[0]=1 だとその前にはおけないんだけど、そのグループの後に置くのと結局同じことなので
    for (int i=1; i<N; ++i) {
      int last = D[i-1], curr = D[i], diff = curr - last;
      if (0 < diff && diff <= 10) {
        dp[i][0] = min4(dp[i-1][0]+3+0, dp[i-1][1]+2+0, dp[i-1][2]+1+0, dp[i-1][3]+0+0); // restart
        dp[i][1] = min4(dp[i-1][0]    , dp[i-1][1]+2+1, dp[i-1][2]+1+1, dp[i-1][3]+0+1);
        dp[i][2] = min4(dp[i-1][0] +1 , dp[i-1][1]    , dp[i-1][2]+1+2, dp[i-1][3]+0+2);
        dp[i][3] = min4(dp[i-1][0] +2 , dp[i-1][1] +1 , dp[i-1][2]    , dp[i-1][3]+0+3);
      }
      else if (10 < diff && diff <= 20) {
        // 1 gap
        dp[i][0] = min4(dp[i-1][0]+3+0, dp[i-1][1]+2+0, dp[i-1][2]+1+0, dp[i-1][3]+0+0); // restart
        dp[i][1] = min4(dp[i-1][0]+3+1, dp[i-1][1]+2+1, dp[i-1][2]+1+1, dp[i-1][3]+0+1);
        dp[i][2] = min4(dp[i-1][0] +1 , dp[i-1][1]+2+2, dp[i-1][2]+1+2, dp[i-1][3]+0+2);
        dp[i][3] = min4(dp[i-1][0] +2 , dp[i-1][1] +1 , dp[i-1][2]+1+3, dp[i-1][3]+0+3);
      }
      else if (20 < diff && diff <= 30) {
        // 2 gaps
        dp[i][0] = min4(dp[i-1][0]+3+0, dp[i-1][1]+2+0, dp[i-1][2]+1+0, dp[i-1][3]+0+0); // restart
        dp[i][1] = min4(dp[i-1][0]+3+1, dp[i-1][1]+2+1, dp[i-1][2]+1+1, dp[i-1][3]+0+1);
        dp[i][2] = min4(dp[i-1][0]+3+2, dp[i-1][1]+2+2, dp[i-1][2]+1+2, dp[i-1][3]+0+2);
        dp[i][3] = min4(dp[i-1][0] +2,  dp[i-1][1]+2+3, dp[i-1][2]+1+3, dp[i-1][3]+0+3);
      }
      else {
        // 前と切って(前を終わらせてから)restart
        dp[i][0] = min4(dp[i-1][0]+3+0, dp[i-1][1]+2+0, dp[i-1][2]+1+0, dp[i-1][3]+0+0);
        dp[i][1] = min4(dp[i-1][0]+3+1, dp[i-1][1]+2+1, dp[i-1][2]+1+1, dp[i-1][3]+0+1);
        dp[i][2] = min4(dp[i-1][0]+3+2, dp[i-1][1]+2+2, dp[i-1][2]+1+2, dp[i-1][3]+0+2);
        dp[i][3] = min4(dp[i-1][0]+3+3, dp[i-1][1]+2+3, dp[i-1][2]+1+3, dp[i-1][3]+0+3);
      }
    }
    int ans = min4(dp[N-1][0]+3, dp[N-1][1]+2, dp[N-1][2]+1, dp[N-1][3]);
    printf("Case #%d: %d\n", 1+_t, ans);
  }
}

終了

蓋を開けてみれば4問とも通っていて、まさかの全完。
ただ、24時間あったから行けただけで、これが2時間半とか3時間とかだったら、焦って(途中までやっては放棄して次に行くなどして)1つも取れなかったりするんだよね…

それではRound 2でお会いしましょう!
Tシャツ取れるといいなあ(先着500名様)

*1:いちいち先に最小時間を求めなくても、priority queueに投入する時刻は各洗濯機に1つずつで良くて、空いたやつだけ再稼働すれば同じものが得られる

*2:Mに最大値(1e9=10億台)が来るとTLEになる。Lが1e6までと分かってるんだから残りの乾燥機は捨て置けばよい