BOJ 29795 한 대

문제 링크입니다.

공격적인 스킬 배치

모든 스킬이 공격력이 높을 수록 효율이 좋습니다. 그리디하게 매 순간 내 공격력을 제일 크게 높이는 스킬을 쓰는 전략이 최적입니다.

각 스킬을 $f_i(x) = a_ix+b_i$ 꼴의 함수로 보고 그래프를 그리면, 각각의 스킬은 하나의 직선으로 표현됩니다. 현재 공격력에 대해 최적의 스킬을 썼을 때의 다음 공격력은 $N$개의 일차함수 중 해당 $x$값에서 가장 높이 있는 직선 위의 점이 됩니다.

이를 모두 합치면 일차함수 무더기의 위쪽 뚜껑을 얻을 수 있고, 이 뚜껑은 아래로 볼록합니다.

이게 돌아요?

CHT로 각 구간에 최적의 스킬을 대응시켜줍니다. 그러면 현재 공격력과 목표 공격력이 주어졌을 때, 공격력이 목표 공격력에 도달할 때까지 최적의 스킬을 써 주면 답을 구할 수는 있습니다.

이제 이걸 시간 안에 해야 하는데, 만약 스킬의 $a$값이 2 이상이라면 매 스킬 사용마다 공격력의 증가량이 $a$배 이상 늘기 때문에 대충 $\log _2 10^{12} \approx 40$번 정도 안에 반드시 목표 공격력에 도달할 수 있습니다.

$a$가 1인 경우는 공격력에 상수를 더해주는 스킬이니, 해당 스킬을 써야 하는 구간을 벗어날 때까지 필요한 스킬 사용 횟수를 바로 구할 수 있습니다.

스킬을 사용한 뒤 다음 구간을 이분 탐색으로 찾아주면 최종적으로 ${\cal O} (N \lg N + Q \lg y \lg N)$의 시간 복잡도에 문제를 해결할 수 있습니다.

코드

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

vector<pair<ll, ll>> skill, s;
vector<ll> changer;

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
	int n, q; cin >> n >> q; skill.reserve(n+1); s.reserve(n+1); changer.reserve(n+1);
	for(int i = 0; i < n; i++){
		ll a, b; cin >> a >> b;
		skill.push_back({a, b});
	}
	sort(skill.begin(), skill.end());
	for(int i = 0; i < skill.size(); i++){
		if(s.empty()) s.push_back(skill[i]);
		else{
			if(s.back().second <= skill[i].second) s.pop_back();
			s.push_back(skill[i]);
		}
	}
	skill.clear();
	for(int i = 0; i < s.size(); i++){
		while(skill.size()){
			ll c = (skill.back().second-s[i].second); c--;
			c /= (s[i].first-skill.back().first); c++;
			if(c <= changer.back()){
				skill.pop_back();
				changer.pop_back();
			}
			else{
				skill.push_back(s[i]);
				changer.push_back(c);
				break;
			}
		}
		if(skill.empty()){
			skill.push_back(s[i]);
			changer.push_back(-123456789123456789);
		}
	}
	while(q--){
		ll x, y; cin >> x >> y;
		ll now = upper_bound(changer.begin(), changer.end(), x)-changer.begin()-1;
		if(x*skill[now].first+skill[now].second <= x){
			cout << "-1\n";
			continue;
		}
		ll ans = 0;
		while(x < y){
			if(skill[now].first == 1){
				ans += ((now == changer.size()-1 ? y : min(y, changer[now+1]))-x-1)/skill[now].second+1;
				x += ans*skill[now++].second;
			}
			else{
				x = x*skill[now].first + skill[now].second;
				ans++;
			}
			now = upper_bound(changer.begin(), changer.end(), x)-changer.begin()-1;
		}
		cout << ans << '\n';
	}
}