[ICPC] 백준 23342 - Histogram

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

서론

대회 때 누적합을 쓰는 dp겠거니 싶어서 시도해봤는데 풀지 못하고 도망쳤었다. 이번에 다른 풀이를 참조했는데 아마 대회 중에는 떠올리지 못했을 것이다.

테이블 설계

이 문제를 dp로 푸는 테이블은 다음과 같다.

 

dp(i, j) := i번째 인덱스에서 버킷이 j개 남았을 때 분산의 최솟값

 

탑 다운 dp로 풀 때는 0부터 시작하는 다른 함수와 달리 n부터 시작하면서 내려가는 방식이다.

분산 구하기

중고등학교 교과 과정을 무사히 이수 했다면 모집단에서 분산을 구하는 식은 다음과 같음을 잘 알고 있다.

 

$\sum(X - m)^{2}$

 

우리는 위 분산 계산을 고속으로 하기 위해 식을 일부 전개 후 누적합을 사용할 것이다.

 

$\sum (X^{2} - 2Xm + m^{2})$

 

그러면 $X$와 $X^{2}$을 빠르게 구할 필요가 있음을 알 수 있고 이는 입력으로 주어진 $f_{i}$들의 합 누적합과 제곱 합 누적합을 구해야 한다.

동적 계획법 수행

누적합으로 처리하면 $O(1)$에 해당 구간의 분산을 구할 수 있다. 그러면 처음 문단에 언급한 점화식을 풀면 $O(N^{2}b)$의 시간복잡도로 풀 수 있다.

 

전체 코드

#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 bu;
int n;
int pref[4001];
int pref2[4001];
int ar[4001];
double dp[4001][31];
 
inline double get_var(int go, int to)
{
  int len = to - go + 1;
  double Xsq = pref2[to] - pref2[go - 1];
  double Xsum = pref[to] - pref[go - 1];
  double mean = Xsum / len;
  return Xsq - 2 * Xsum * mean + mean * mean * len;
}
 
double memo(int cur, int buckets)
{
  auto &ret = dp[cur][buckets];
 
  if (ret != 1e100) return ret;
  ret = 0;
 
  if (buckets == 1) return ret = get_var(1, cur);
 
  double tmp = 1e100;
 
  for (int i = cur; i >= buckets; i--)
  {
    tmp = min(tmp, memo(i - 1, buckets - 1) + get_var(i, cur));
  }
 
  return ret = tmp;
}
 
void solve()
{
  cout.precision(10);
  cout << fixed;
 
  fill(&dp[0][0], &dp[0][0] + 4001 * 31, 1e100);
 
  cin >> bu >> n;
 
  if (bu >= n)
  {
    cout << 0;
    return;
  }
 
  for (int i = 1; i <= n; i++)
  {
    cin >> ar[i];
    pref[i] = pref[i - 1] + ar[i];
    pref2[i] = pref2[i - 1] + ar[i] * ar[i];
  }
 
  cout << memo(n, bu);
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록