「みんなのプロコン」本選 B問題 - チーム決め

Source

「みんなのプロコン」本選
「みんなのプロコン」本選 オープンコンテスト
問題文

問題概要

$2$ つの $r$ 人からなるチームに対して，それぞれのチームメンバーの実力を昇順に $x_1,x_2,\ldots,x_r$ と $y_1,y_2,\ldots,y_r$ とした時，チームの実力差を
\[ \max_{i=1,2,\ldots,r} |x_i - y_i| \]で定義する．
高橋さんという名前の人が $N$ 人いて，その実力は $A_1,A_2,\ldots,A_N$ である．
青木さんという名前の人が $M$ 人いて，その実力は $B_1,B_2,\ldots,B_M$ である．
高橋さん $K$ 人と，青木さん $K$ 人を選んでチーム高橋とチーム青木を作る時，チームの実力差の最小値を求める問題．

解法

実力差が $c$ 以下となるようにチームメンバーを最大何人選べるか？という問題は貪欲法で解けるので，答えに対して二分探索する．
それは，各チームで実力が最小の人の実力差が $c$ 以下ならそれらをメンバーに加えて，そうでなければ，実力の低い方はどうやってもメンバーになれないので解雇する，というのを繰り返せば良い．
時間計算量は $O((N+M) \log (N+M) \log \max(A_i,B_i))$ 程度．

cLay（version 20170326-2）のコード

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

int K, As, Bs, A[100000], B[100000];
{
  int i, j, ok;
  int X, Y, C;
  
  rd(As,Bs,K,A(As),B(Bs));
  sort(A, A+As);
  sort(B, B+Bs);

  X = 0;
  Y = int_inf;
  while(X < Y){
    C = (X+Y) / 2;
    ok = 0;

    i = j = 0;
    while(i < As && j < Bs){
      if( abs(A[i]-B[j]) <= C ){
        ok++; i++; j++;
        if(ok == K) break;
        continue;
      }
      if(A[i] < B[j]) i++; else j++;
    }

    if(ok >= K) Y = C; else X = C+1;
  }

  wt(X);
}

Current time: 2024年04月24日19時02分05秒
Last modified: 2017年03月26日11時07分11秒 (by laycrs)
Tags: Competitive_Programming AtCoder yahoo-procon2017-final
トップページに戻る

Logged in as: unknown user (not login)

ログイン：