백준 2912 - 백설공주와 난쟁이

https://www.acmicpc.net/problem/2912

필요 지식

이 포스트에서는 머지 소트 트리를 사용하며 약간의 수학적 통찰력이 필요하다. 모스 알고리즘 같은 다른 풀이는 다루지 않는다.

아이디어

A번째 난쟁이와 B번째 난쟁이까지를 하나의 구간으로 보자.

 

그러면 이 구간에서 절반을 초과하는 색깔(이하 과반수)이 존재하는지 구해야 한다.

 

구간에서 어떤 원소 하나를 선택한다고 해보자. 이 색깔이 과반수일 확률은 $\frac{1 + \epsilon}{2}$이라는 것은 바로 이해할 수 있다.

 

반대로 과반수가 아닐 확률은 $\frac{1 - \epsilon}{2}$가 된다는 뜻이다.

 

그러면 원소를 r번 선택했을 때 과반수가 아닐 확률은 $(\frac{1 - \epsilon}{2})^{r}$가 된다.

 

여기서 r이 조금만 커져도 확률이 지수적으로 엄청나게 작아짐을 알 수 있고 우리는 적당한 r번만큼 구간 내 원소를 랜덤 선택해서 과반수인지 확인하면 높은 확률로 옳은 결과를 찾을 수 있음을 짐작할 수 있다.

 

머지 소트 트리로 각 정렬된 구간을 만들면서 20번 정도 구간 내 원소 중 하나를 랜덤으로 선택하여 과반수인지 확인하고 확인 결과에 따라 적절한 출력을 하면 정답을 받을 수 있다.

 

Overall Time Complexity: $O(rN \log^{2} N)$

 

전체 코드

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = long long;
using pii = pair<int, int>;
 
int n, c, q;
vector<int> mst[1200000];
int ar[300001];
 
void init(int node, int start, int end)
{
  if (start == end)
  {
    mst[node].push_back(ar[end]);
    return;
  }
 
  int m = start + (end - start) / 2;
  init(node * 2, start, m);
  init(node * 2 + 1, m + 1, end);
  int leng = mst[node * 2].size() + mst[node * 2 + 1].size();
  mst[node].resize(leng);
 
  merge(mst[node * 2].begin(), mst[node * 2].end(), mst[node * 2 + 1].begin(), mst[node * 2 + 1].end(), mst[node].begin());
}
 
int query(int node, int start, int end, int l, int r, int item)
{
  if (start > r or end < l) return 0;
  if (l <= start and end <= r)
    return upper_bound(mst[node].begin(), mst[node].end(), item) - lower_bound(mst[node].begin(), mst[node].end(), item);
  int m = start + (end - start) / 2;
 
  return query(node * 2, start, m, l, r, item) + query(node * 2 + 1, m + 1, end, l, r, item);
}
 
void solve()
{
  cin >> n >> c;
  
  for (int i = 1; i <= n; i++)
  {
    cin >> ar[i];
  }
 
  init(1, 1, n);
 
  cin >> q;
 
  while (q--)
  {
    int go, to;
    cin >> go >> to;
 
    int bound = (to - go + 1) / 2;
    int sz = to - go + 1;
 
    int res = -1;
 
    srand(q + 1);
    for (int i = 0; i < 24; i++)
    {
      int idx = rand() % sz + go;
 
      int x = query(1, 1, n, go, to, ar[idx]);
 
      if (x > bound)
      {
        res = ar[idx];
        break;
      }
    }
 
    if (res == -1)
    {
      cout << "no\n";
    }
    else
    {
      cout << "yes " << res << '\n';
    }
  }
}
 
int main()
{
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록

보너스

사실 이 문제는 머지 소트 트리를 쓰지 않고도 풀 수 있다. 심지어 실행 시간은 더 빠를 것이다.

 

https://www.acmicpc.net/problem/10124

10124번: Couriers

 

사실상 같은 문제지만 머지 소트 트리를 사용하면 해결할 수 없다. 너무 무겁기 때문이다. 머지 소트 트리를 안 써도 되는 이유를 생각해보고 이 문제를 해결해보자.