Google Code Jam 2017 Qualification Round C問題 - Bathroom Stalls

Source

Google Code Jam 2017 Qualification Round C問題
Problem Statement

問題概要

$N+2$ 個のトイレが一列に並んでおり，両端のトイレは最初から使われている．
トイレは左から $0,1,2,\ldots,N,N+1$ と番号がつけられている．
次々と $K$ 人の人が来て，次のようなアルゴリズムで使うトイレを決める．
各トイレ $i$ に対して，そのトイレから左方向に最初に使われているトイレまでの距離 $L_i$，および，そのトイレから右方向に最初に使われているトイレまでの距離 $R_i$ を計算する．
$\min(L_i,R_i)$ が最も大きいもの，その中で，$\max(L_i,R_i)$ が最も大きいもの，更に，その中で一番左のトイレを選んで使う．
途中で人が帰ることはない．
$K$ 番目の人が選ぶトイレ $s$ に対して，その時の $\max(L_s,R_s), \min(L_s,R_s)$ の値を求める問題．

解法

要するに，それぞれの人は，一番長い空き区間の真ん中のあたりを選ぶ，というアルゴリズムである．
よって，区間の長さだけを保持してシミュレーションすれば良い．
一番長い区間が長さ $100$ の空き区間だったら，人が $1$ 人来たら，長さ $50, 49$ の区間に分かれる，
一番長い区間が長さ $101$ の空き区間だったら，人が $1$ 人来たら，長さ $50, 50$ の区間に分かれる，という感じ．
出てくる区間の長さの種類はあまりないので，区間の長さと，その長さの区間の数を管理して，同じ長さの区間に関してはまとめて処理をしてやれば十分高速にできる．
時間計算量は $O(\log K)$ 程度．

cLay（version 20170408-3）のコード

C++に変換後のコードはこちら

{
  int test = 0, TEST;
  rd(TEST);
  while(TEST--){
    printf("Case #%d: ", ++test);
    fprintf(stderr, "r=%d\n", TEST);

    ll N, K;
    ll now, sz;
    priority_queue< pair<ll,ll> > q;
    
    rd(N, K);
    K--;
    
    q.push( make_pair(N, 1LL) );
    for(;;){
      now = q.top().first;
      sz = 0;
      while(q.size() && q.top().first == now){
        sz += q.top().second;
        q.pop();
      }
      if(K < sz) break;

      K -= sz;
      q.push( make_pair( now/2, sz) );
      q.push( make_pair( (now-1)/2, sz) );
    }

    wt(now/2, (now-1)/2);
  }
}

Current time: 2024年04月26日06時43分31秒
Last modified: 2017年04月14日00時56分00秒 (by laycrs)
Tags: Competitive_Programming Google_Code_Jam GCJ_2017 GCJ_2017_Qualification_Round
トップページに戻る

Logged in as: unknown user (not login)

ログイン：