BOJ 18622 Dedenne

BOJ 18622 Dedenne (GP of Warsaw, Petrozavodsk Programming Camp Summer 2019 Day 5 #D)

 

3일 정도에 걸쳐 5시간정도 고민했고, 찾아낸 풀이가 매우 인상적인 문제였다. 우와 정말 데덴네~

 

 

 

문제 설명

 

쿼리 $T$개가 주어진다. ($1 \leq T \leq 50000$)

 

각 쿼리마다 정수 $N$이 하나씩 주어지는데, 문제에서 주어진 Cost가 최소가 되도록 조건에 맞게 $N$개의 Binary String을 선택해야 한다. ($2 \leq N \leq {10}^{15}$)

 

조건은

1. 선택한 모든 Binary String에서 연속한 두 자리에 모두 0이 올 수 없다.

2. 선택한 한 Binary String이 다른 Binary String의 Prefix가 될 수 없다.

 

Cost는 $f(x)=\sum_{j=1}^{x} {[1+{log}_{2}{j}]}$이라 할 때, 모든 Binary String에 대하여 이 문자열이 자신이 선택한 Binary String들의 Prefix로 오는 횟수를 $k$회라 하면 $f(k)$들의 총합이다.

 

 

 

풀이

 

1. $O({N}^{2})$

 

입력된 $n$에 대한 최소 Cost를 $g(x)$이라 하면, $g(x)=f(x)+\min_{1\leq i<n}(g(i)+f(i)+g(x-i))$라는 점화식을 간단하게 도출할 수 있다.

이를 Naive하게 계산해 준다면 $O({N}^{2})$의 시간에 $g(x)$를 모두 구할 수 있다.

 

 

2. $O(NlogN)$

 

함수 $g(x)$가 Convex함을 보이자.

우선 $f(x)$가 Convex함은 자명하다.

$\forall x\leq n, x\in \mathbb N$에 대하여 $g(x)$가 Convex하다고 가정하자.

$x\leq n$일 때 고정된 i에 대하여 $(g(i)+f(i)+g(x-i))$는 Convex하다.

$\min_{1\leq i<n}$$(g(i)+f(i)+g(x-i))$는 Convex한 함수들의 최솟값이므로 마찬가지로 x에 대하여 Convex하다.

따라서, $\forall x\leq n+1, x\in \mathbb N$에 대하여서도 $g(x)$는 Convex하다.

수학적 귀납법에 의하여 $\forall x\in \mathbb N$에 대하여 $g(x)$는 Convex하다.

증명에 오류가 있습니다. 추후 수정하도록 하겠습니다.

 

$g(x)$가 Convex함을 보였기 때문에, $1\leq n \leq x$인 모든 $n$에 대한 $g(x), f(x)$값을 가지고 있다면 삼진 탐색을 통해서 $O(logN)$의 시간에 $g(x+1)$을 구할 수 있음을 알 수 있다.

따라서 총 $O(NlogN)$의 시간복잡도로 $g(x)$를 모두 구할 수 있다.

 

 

3. $O(M{log}^{3}N+TlogM)$

 

$n$의 범위가 $10^{15}$이므로 $O(NlogN)$에서 시간을 더 줄여야 한다.

 

"기울기가 변하는 횟수가 충분히 적다면 기울기가 변하는 점이랑 그 때의 함숫값, 기울기를 미리 다 구해놓을 수 있지 않을까?"라는 발상을 해보자. (...)

 

이를 실제로 구해보는 것은 어렵지 않다. 배열에 위에서 언급한 값들의 초기값을 저장해두고, 이분 탐색을 통해 마지막으로 추가한 점 다음의 기울기가 변하는 점을 구해서 $10^{15}$ 이전까지 계속 추가해 나가면 된다.

다음으로 기울기가 변하는 점을 찾는데는 이분 탐색에 $logN$, 삼분 탐색에 $logN$, $f(x)$값을 구하는 데 $logN$이 걸리므로 총 $O({log}^{3}N)$의 시간이 걸린다.

 

구현하여 실행해 보면, 기울기가 변하는 점의 수는 $10^{15}$ 이전에 총 1833개가 나타난다. (위의 시간 복잡도의 $M$은 1833이다.)

 

이제 쿼리로 주어지는 각 $t$에 대해서는 $t$ 이전에 마지막으로 기울기가 변하는 점을 std::lower_bound 등을 이용해 구하여 쉽게 계산할 수 있다.

 

 

Sample Code

아래의 코드는 BOJ 기준 940ms 정도에 작동하였다.

#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;
using ll = long long;

const ll MX = 1e15;

ll f(ll x) {
	ll r=0;
	for (int i=0; ; i++) {
		if ((1ll<<i+1)>x) return r+(x-(1ll<<i)+1)*(i+1);
		r+=(1ll<<i)*(i+1);
	}
}

vector<ll> P, S, T;

ll g1(ll n) {
	int b=upper_bound(P.begin(), P.end(), n)-P.begin()-1;
	return T[b]+S[b]*(n-P[b]);
}

ll g2(ll n) {
	ll s=1, e=n-1;
	while (s+3<e) {
		ll x1=(s*2+e)/3, x2=(s+e*2)/3;
		ll v1=g1(x1)+g1(n-x1)+f(x1), v2=g1(x2)+g1(n-x2)+f(x2);
		if (v1>v2) s=x1;
		else e=x2;
	}
	ll mn=g1(n-1)+1;
	for (ll i=s; i<=e; i++) mn=min(mn, g1(i)+g1(n-i)+f(i));
	return mn+f(n);
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	P.eb(1); S.eb(4); T.eb(1);
	while (1) {
		ll s=P.back()+1, e=1e16;
		while (s<e) {
			ll m=(s+e+1)/2;
			ll x=g1(m), y=g2(m);
			if (x!=y) e=m-1;
			else s=m;
		}
		if (s>MX) break;
		T.eb(T.back()+(s-P.back())*S.back());
		S.eb(g2(s+1)-g1(s));
		P.eb(s);
	}
	int T; ll N; cin>>T;
	while (T--) cin>>N, cout<<g1(N)<<'\n';
	return 0;
}