KOI 2019 1차 고등부 2번 점프

문제 링크 : https://www.acmicpc.net/problem/17613

문제 풀이

일단 문제를 한 번 보자. "만일 점프간격을 2배씩 계속 증가시켜 마지막 점프에서 목표 수 x를 지나칠 것 같으면, 필요한 경우 언제든지 점프 간격을 다시 처음 상태인 간격 1로 되돌아 갈 수 있다. 이것을 재시작이라고 부른다." 라는 문구가 굉장히 중요한 부분이다. 굳이 이 문구를 통해서 유추를 할 필요는 없지만, 풀이를 생각하는 과정에서 이 문장은 풀이의 일부에 확신을 주게 된다.

Phase 1

현재 개구리가 $2^i$ 까지 한 번에 뛰었다. 그리고 $2^{i+1}$을 뛸 수 있는 상황이다. 그런데 안 뛸 이유가 있을까? $2^{i+1}$은 1부터 $2^i$까지의 합보다 크다. 1번의 점프로 i번의 점프의 효과보다 더 크게 낼 수 있다. 따라서 무조건 $2^{i+1}$을 뛸 수 있다면 무조건 뛰는 것이 이득이다. - 관찰 1

따라서 위치 k까지 갈 때는 맨 처음에 무조건 $\sum_{i=0}^{j}2^{i}\leq k$인 최대 2^j까지 행동하는 것이 맞다. 이때의 합은 $2^{j+1}-1$이 될 것이다.

어떠한 k에 대해서 무조건 행동해야하는 부분이 나왔으므로, 나머지 부분을 어떻게 행동해야 하는지에 대한 문제를 풀면 된다. 정확히는 k대신에 $k-(2^{j+1}-1)$ 을 넣고 문제를 풀면 된다. 따라서 이 문제는 DP를 통해서 해결할 수 있을 것 처럼 보인다. 

좀 더 정확히 쓰자면 DP[k]를 k까지 가는데 걸리는 횟수라고 하면 DP[k]=DP[$k-(2^{j+1}-1)$]+j+1이다.

Phase 2

하지만 이 문제는 범위와 쿼리로 이루어져 있다. 그 와중에 범위는 10^9이기 때문에 log 스케일로 풀어야 한다. Phase 1의 풀이를 다시보자. DP를 log에 풀기 위해서는 그룹으로 묶어야 한다. 그리고 우리는 그룹으로 묶기에 좋은 수단을 가지고 있다. $2^k-1$ ~ $2^{k+1}-1$ 은 모두 같은 행동을 초반에 하게 된다. 

위와 같이 그룹을 묶었다고 하자. 일단 우리는 쉽게 각 그룹별로 DP의 최댓값을 구할 수 있다. NEWDP[k]를 정의해서 $2^k-1$ ~ $2^{k+1}-1$ 중 에서 DP의 최댓값이라고 정의하자. 이때 저 범위에서는 모두 k+1번의 횟수를 사용하여 $2^k-1$ 만큼 이동하기 때문에 범위는 0에서 $2^k-1$ 까지의 범위에 k+1을 더한 값이 된다. 즉, NEWDP[k-1]+k+1이 NEWDP[k]가 된다.

문제에서 구간의 답을 구할 때에는 이미 구해진 구간을 이용하면 된다. 이미 구해놓은 구간 s~e에 대해서 s~e가 완벽히 포함되어 있으면 구해놓은 답을 사용하면 되고, 일부만 포함되어있으면 그 일부를 재귀적으로 다시 바꿔서 문제를 해결할 수 있다. 자세한 내용은 코드 참고

풀이 정리

1. 어떤 위치에 도달할 때까지 당연히 가능한 최대치까지 이동을 해야 된다.

2. 한 번에 뛴 최대 거리를 기준으로 범위를 나눈다. 

3. 각 그룹별로 그룹내의 최대 횟수 값을 미리 구한다.

4. 미리 구한 값을 이용하여 재귀적으로 구간 쿼리를 처리한다.

코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
#define ff first 
#define ss second
#define pb push_back
 
ll dp[32];
vector<ll> v;
ll sol(ll a,ll b){
    a=max(a,1LL);
    if(a>b) return 0;
    ll ret=0;
    ll st=upper_bound(v.begin(), v.end(),a)-v.begin()-1;
    for(ll i=st;i<=31;i++){
        ll s=max(v[i],a);
        ll e=min(v[i]*2,b);
        if(s>b) break;
        if(e==s*2) ret=max(ret,dp[i+1]);
        else ret=max(ret,sol(s-v[i],e-v[i])+i+1);
    }
    return ret;
}
 
int main(){
    ll t;
    ll i,j,k,l,m,n,mx=2;
    scanf("%lld",&t);
    v.pb(1);
    dp[1]=2;
    for(i=2;i<=31;i++){
        v.pb((1<<i)-1);
        dp[i]=max(2*i,mx+i);
        mx=max(mx,dp[i]);
    }
    while(t--){
        ll i,j,k,l,m,n;
        scanf("%lld %lld",&n,&m);
        printf("%lld\n",sol(n,m));
    }
}