AtCoder ABC294 F - Sugar Water 2

ABC294 - F

이분 탐색은 알았는데, 결정 함수를 짜는 방법을 모르겠어서 에디토리얼을 참고했다.

아이디어

우리가 정답인 농도를 이분탐색으로 구하는데, $NM$개의 조합 중, 현재 보고 있는 농도 $x$보다 높은 것의 개수를 구한다.

그것이 $k$ 이상이라면 $x$를 더 높여주고, 아니면 낮춰주면서 정답을 찾아낸다.

결정 함수

$x$의 농도에 대해 $NM$개의 조합의 농도 중 몇개가 $x$보다 작을까?

설탕물이 $s$의 설탕과 $t$의 물로 이루어져 있다고 하자.

이것이 $x$가 되는 설탕의 양을 $u=t \dfrac x{1-x}$ 로 정의한다.

실제로 그런것은 아니지만 물에 있는 설탕의 비율을 $\dfrac x{1-x}$ 로 두어도 문제없다.

농도는 $100$ 같은 상수를 제거하고 ratio만 따져도 충분하다.

이제 여기서 $s \ge u$ 라면 $s-u$ 그램의 설탕이 더 있다는 것이고

$s < u$ 라면 $u-s$ 의 설탕이 부족하다는 것이다.

$u-s$의 설탕이 부족하다는 것을 $s-u$ 만큼의 음의 설탕이 더 있다고 재정의함으로써, 우린 항상 $s-u$ 만큼의 설탕에 대해서만 다룰 수 있다.

매번 결정함수마다 다음과 같은 작업을 한다.

• $(v_1,\,v_2, \dots , v_M)$ 을 Aoki가 가진 설탕물들에 대해서 $(s-u)$ 라고 하자.
• $v$ 를 정렬한다.
• Takahashi의 설탕물들을 다음과 같이 처리한다.
  • $w$를 현재 설탕 물의 $(s-u)$라고 하면, Aoki가 가진 것 중 $v_i$ 가 최소 $-w$ 이상이여야 $x$이상의 농도가 나오므로 이분 탐색으로 개수를 찾아주면 된다.

코드

void solve() {  
   int n, m, k;  
   cin >> n >> m >> k;  
   vector<pi> ab(n), cd(m);  
   for (auto&[a, b]: ab) cin >> a >> b;  
   for (auto&[c, d]: cd) cin >> c >> d;  
  
   double L = 0, R = 1;  
   for (int i = 0; i < 100; i++) {  
      double M = L + (R - L) / 2;  
      int ge_cnt = 0;  
  
      double u = M / (1 - M);  
      vector<double> v(m);  
      for (int i = 0; i < m; i++)  
         v[i] = cd[i].fi - cd[i].se * u;  
      sort(all(v));  
  
      for (int j = 0; j < n; j++) {  
         double w = ab[j].fi - ab[j].se * u;  
         ge_cnt += m - lbi(v, -w);  
      }  
      (ge_cnt < k ? R : L) = M;  
   }  
   cout.precision(15);  
   cout << fixed << L * 100;  
}

후기

이 문제에서 놓쳤던 것은 결정 함수의 작성에서 $x$ 에 대해서 한 번의 결정함수마다 무언가 정렬을 새롭게 해줄 수 있다는 사실이다.

이런 테크닉은 처음 알았다.

아예 이분 탐색이 들어가기 전에 어떻게든 $C,D$ 배열을 먼저 정렬해두고 풀어야 된다는 생각이 있었고, 그것이 못 푼 원인이다.