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

naoya_t@hatenablog

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

Google Code Jam 2017 - Round 1C

f:id:n4_t:20170501012223p:plain
A-small/large, B-small/large, C-small-1まで通して、ようやく Round 2 & Distributed Code Jam 進出。
(72点, 438位)

A. Ample Syrup

https://code.google.com/codejam/contest/3274486/dashboard#s=p0

small (9pt) / large (16pt)
  • 表面積の合計=一番大きい(=一番下に置かれる)パンケーキの平らな面1つ分の面積と、全パンケーキの側面の面積の合計
  • 一番下に置くやつを1つ(総当りで)選んで、それより小さいもので側面面積が大きい順にK個選んで表面積合計を計算。で一番大きいやつ。
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <numeric>
#include <string>
#include <vector>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <cassert>
using namespace std;

typedef long long ll;
#define sz(a)  int((a).size())
#define pb  push_back
#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++)
#define found(s,e)  ((s).find(e)!=(s).end())

typedef pair<int,int> ii;
typedef pair<double,double> dd;

#define PI 3.14159265358979323846

int main(){
  int _T; cin>>_T;
  rep(_t,_T){
      int N, K; cin >> N >> K;
      vector<dd> q;
      rep(n,N){
          int r, h;
          cin >> r >> h;
          double s = PI*2*r*h;
          double t = PI*r*r;
          q.push_back(dd(s,t));
      }

      double ans = 0.0;

      for (int i=0; i<N; ++i) {
          double top = q[i].second;
          priority_queue<double> pq;
          for (int j=0; j<N; ++j) {
              if (j == i) continue;
              if (q[j].second > top) continue;
              pq.push(q[j].first);
          }

          double side = q[i].first;
          for (int k=1; k<K; ++k) {
              if (pq.empty()) break;
              double s = pq.top(); pq.pop();
              side += s;
          }

          ans = max(ans, top + side);
      }

 answer:
    printf("Case #%d: %.7f\n", 1+_t, ans);
  }
}

B. Parenting Partnering

https://code.google.com/codejam/contest/3274486/dashboard#s=p1

small (12pt)

アクティビティ数は(C,Jの)2人で合計1か2のいずれかなので場合分けで。
・合計1なら交代2回。
・合計2なら、1つずつなら2回。2つを1人だけがやる場合、2つのアクティビティを(短い方で)繋いで12時間に収まるなら2回。収まらないなら4回。

(略)
typedef pair<int,int> ii;

int A2(vector<ii>& C) {
    int w0 = C[1].second - C[0].first;
    if (w0 <= 720) return 2;
    int y0 = C[1].first - C[0].second;
    if (y0 >= 720) return 2;

    int w1 = 1440+C[0].second - C[1].first;
    if (w1 <= 720) return 2;
    int y1 = 1440+C[0].first - C[1].second;
    if (y1 >= 720) return 2;

    return 4;
}

int solve_s(vector<ii>& C, vector<ii>& J) {
    int Ac = C.size(), Aj = J.size();
    if (Ac + Aj == 1) {
        return 2;
    } else if (Ac + Aj == 2) {
        if (Ac == 2 && Aj == 0) {
            return A2(C);
        } else if (Ac == 0 && Aj == 2) {
            return A2(J);
        } else {
            return 2;
        }
    }
    return 0;
}

int main(){
  int _T; cin>>_T;
  rep(_t,_T){
      int Ac, Aj; cin >> Ac >> Aj;
      vector<ii> C(Ac), J(Aj);
      rep(i, Ac) {
          int s, e; cin >> s >> e;
          C[i] = ii(s, e);
      }
      sort(all(C));
      rep(i, Aj) {
          int s, e; cin >> s >> e;
          J[i] = ii(s, e);
      }
      sort(all(J));

      int ans = solve_s(C, J);
 answer:
    cout << "Case #" << (1+_t) << ": " << ans << endl;
  }
}
large (20pt)

(後回しにして、C-small-1を先にやってから)ちゃんと考えた。
・キャメロンのアクティビティ(C)とジェイミーのアクティビティ(J)を、一緒に時系列にソート。
・各インターバル(C-J, J-C, C-C, J-J の4通りある)間に交代をどう入れるか。C-J, J-C間には奇数回(1, 3, 5, ...)の交代、C-C、J-J間には偶数回(0, 2, 4, ...)の交代が入るはずだが。奇数回は1回の交代で十分(インターバルを2人に都合よく割り振る)。偶数回は0(インターバル中ずっともう1人が子守を引き受ける)か2(インターバルの中から好きなだけの分数だけ自分が子守を引き受ける)で。
・1人1人のアクティビティの合計時間を求める。自分のアクティビティの時間は相手が子守をする時間である。そしてそれぞれあと何分ずつ子守を引き受ければいいか求めておく。(それぞれ12時間(720分)ずつ子守を担当しなければならない)。
・各インターバルの分数を計算しておく。(C-J, J-C は同一視してよい)
・C-J, J-C の回数の合計が最低交代回数。
・とりあえず、C-C, J-J間で交代しないものと仮定し、そのインターバルの分数はそれぞれ相手に割り振る。
・交代回数を変えずに時間の割り振りを調整可能な C-J, J-C 間のインターバルは別に合計する。
・持ち時間の少ない方が、720分になるまでインターバルを取っていく。まずはC-J, J-C から。ここで720分に到達できるなら先述の最低交代回数で行ける。
・C-J, J-C間のインターバルを全部取っても720分に満たない場合、C-C(ないしJ-J)からいくらかずつ譲ってもらう。1区間につき交代回数2回が加算されるので、譲ってもらう区間数は少ないほうがいい。なので大きい順に貪欲に。

(略)
typedef pair<int,int> ii;

int solve_l(vector<ii>& C, vector<ii>& J) {
    vector<pair<ii,int> > B;

    int Ac = C.size(), Aj = J.size();
    int sc = 0, sj = 0;

    rep(i, Ac) {
        B.push_back(make_pair(C[i], 0));
        sc += C[i].second - C[i].first;
    }
    rep(i, Aj) {
        B.push_back(make_pair(J[i], 1));
        sj += J[i].second - J[i].first;
    }
    sort(all(B));
    int Ab = Ac + Aj;

    int ans = 0;

    int good = 0;
    vector<int> spC, spJ;

    assert(0 <= sc && sc <= 720);
    assert(0 <= sj && sj <= 720);
    int _total = sc + sj;
    rep(i, Ab) {
        int i1 = (i+1) % Ab;
        int interval = B[i1].first.first - B[i].first.second;
        if (interval < 0) interval += 1440;

        if (B[i].second != B[i1].second) {
            good += interval;
            ++ans;
        } else {
            if (B[i].second == 0) {
                spC.push_back(interval);
                sc += interval;
            } else {
                spJ.push_back(interval);
                sj += interval;
            }
        }
        _total += interval;
    }
    assert(_total == 1440);
    sort(all(spC)); reverse(all(spC));
    sort(all(spJ)); reverse(all(spJ));

    if (720-min(sc, sj) <= good) return ans;

    assert(720-min(sc,sj) > good);
    if (sc > sj) {
        swap(sj, sc);
        swap(spC, spJ);
    }

    sc += good;

    assert(0 <= sc && sc <= 720);

    for (int i=0; i<spJ.size(); ++i) {
        if (sc == 720) break;
        int j = spJ[i];
        sc += j;
        ans += 2;
        if (sc >= 720) break;
    }
    return ans;
}

int main(){
  int _T; cin>>_T;
  rep(_t,_T){
      int Ac, Aj; cin >> Ac >> Aj;
      vector<ii> C(Ac), J(Aj);
      rep(i, Ac) {
          int s, e; cin >> s >> e;
          C[i] = ii(s, e);
      }
      sort(all(C));
      rep(i, Aj) {
          int s, e; cin >> s >> e;
          J[i] = ii(s, e);
      }
      sort(all(J));

      int ans = solve_l(C, J);
 answer:
    cout << "Case #" << (1+_t) << ": " << ans << endl;
  }
}

C. Core Training

https://code.google.com/codejam/contest/3274486/dashboard#s=p2

small-1 (15pt)

・p_i は定数、U = Σx_i として、max Π(p_i + x_i) を求めたい。(これってラグランジュの未定乗数法?F = Π(p_i + x_i) - λ(Σx_i - U) として x_i, λ で偏微分したやつが0になる、みたいな)
・で、*多分* (p_i + x_i) が可能な限り均等になってるのが最強。但しp_i, x_iは非負数。
・U を均等に、というか足りないところに埋めていく。でこぼこな地形に水を流し込む感じで、水を全部入れ終わった時の水面の高さを求めるのは二分探索で。

(略)
typedef pair<int,int> ii;

int main(){
  int _T; cin>>_T;
  rep(_t,_T){
      int N, K; cin >> N >> K;
      double U; cin >> U;
      vector<double> P(N);
      rep(n, N) cin >> P[n];
      sort(all(P));

      double l=0.0, h=1.0000001, p;
      rep(i, 100) {
          if (h-l < 1e-9) break;
          double m = (l+h)/2;
          double s = 0, u = 0;
          p = 1.0;
          rep(j,N) {
              if (P[j]>=m) {
                  s += P[j]; p *= P[j];
              } else {
                  s += m; p *= m;
                  u += m-P[j];
              }
          }
          if (u > U) {
              h = m;
          } else {
              l = m;
          }
      }

 answer:
    printf("Case #%d: %.7f\n",1+_t, p);
  }
}
small-2 (28pt)

・N台の上位K台についてのみ埋めればいいのか?仮にそうだとして、その場合の確率ってどう求める?50C25通りの足し合わせだけどDPで行けるような行けないような…
(提出なし)

終了後

A-large, B-large両方通ってて72pts。終了前481位→438位。
無事通過。
ボーダーはA-large, B-largeまで解いて57点、で早いもの勝ち。(57点取ってても15人あぶれた)C-smallを取ってA-largeを落とすタイプ(56点)だと足りない。
ダッシュボード脇のTop Scoresがいつまで経っても100で埋まらない、と思ってたら、全完してたの8人だけだった(うち2人が日本人)。