yukicoder No.320 眠れない夜に

問題

問題概要

省略

解法

分枝限定法で解けるみたい。n=1とn=2の時は間違えることはないので、nの時フィボナッチ数列の値を求めるまでに、n-2回間違える可能性がある。それを全探索すると、2ⁿ 通り調べなくてはならなくなり、TLEしてしまう。そこで枝刈り的なことができるみたい。今回の問題では、フィボナッチ数列のk項目とk-1項目がわかっていれば、n項目で可能性のある値の上限と下限が求まる。この値の間にに求める値mが含まれていなければ、今のk項目とk-1項目の値からn項目に答えが求まる可能性はゼロである。よってこの値を枝刈りしてこれ以上調べないことにする。つまり、間違える間違えないの２通りの２分岐を考えて、探索していき、条件を満たす可能性がなくなったら、それ以上調べるのをやめることで計算量を落とせるみたい。
参考サイト

Yukicoder No.320 眠れない夜に · うさぎ小屋

ミス

動的計画法かなーとおもったけどできなかった。 分枝限定法を初めて知った。01ナップザック問題の例が多くのっていた。ナップザック問題の場合、解の範囲を、貪欲法と線形計画緩和によって、求まった値を範囲としている?　まあ解の範囲が先に求まっているなら、その値から枝刈りできるよねっていうのがコンセプト?
分枝限定法の参考

http://dopal.cs.uec.ac.jp/okamotoy/lect/2013/opt/handout05.pdf

コード

#include <iostream>
#include <tuple>
#include <vector>
#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
const int INF = 1e9;
#define rep(i,n) for(int i=0;i<(n);i++)

// のこり n 回　普通のフィボナッチ数列をやった場合いくつになるかを求める
ll upper(ll a, ll b, ll n){
    vector<ll> dp(n + 10);
    dp[0] = a, dp[1] = b;
    for (int i = 2; i < n + 2; ++i)
    {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n + 1];
}
// のこり n 回　毎回 -1 するフィボナッチ数列をやった場合いくつになるかを求める
ll lower(ll a, ll b, ll n){
    vector<ll> dp(n + 10);
    dp[0] = a, dp[1] = b;
    for (int i = 2; i < n + 2; ++i)
    {
        dp[i] = dp[i - 1] + dp[i - 2] - 1;
    }
    return dp[n + 1];
}

map<tuple<ll, ll, int, ll>, int> memo;

// fib3 = fib2(b) + fib1(a) n:残りの回数　m:目指す値
int branch_and_bound(ll a, ll b, int n, ll m){
    auto key = make_tuple(a, b, n, m);
    if(memo.count(key)) return memo[key];

    if(n == 0){
        if(b == m){//正解
            return memo[key] = 0;//間違えたの　0回
        }else{
            return memo[key] = INF;
        }
    }

    // どんなに間違えなくても、mに達しない　(上界)
    if(upper(a, b, n) < m){
        return memo[key] = INF;
    }
    //どんなに間違えても、mより小さくできない　(下界)
    if(lower(a, b, n) > m){
        return memo[key] = INF;
    }

    //普通のフィボナッチ数列
    int ret1 = branch_and_bound(b, a + b, n - 1, m);
    //-1したフィボナッチ数列
    int ret2 = branch_and_bound(b, a + b - 1, n - 1, m) + 1;
    //間違える回数が少ないほうを選択
    return memo[key] = min(ret1, ret2);

}

int main(void){
    int n;
    ll m;
    cin >> n >> m;
    int ret = branch_and_bound(1, 1, n - 2, m);
    if(ret == INF){
        printf("-1\n");
    }else{
        printf("%d\n", ret);
    }
    return 0;
}