AOJ 2826 ゲームバランス

問題

ゲームバランス
これD問題らしい。まじ？

考察

最終的には、最大値のパラメータを求めれば良い。

・ある,について、レベルの増加値 : が最大となる敵を倒しても回以上戦闘しなければならない。ただし、倒せる敵はという条件を満たす。

・レベルの増減値を最大とするには、できるだけ自分のレベル に近い敵を倒せば良い。これは、二分探索で高速に求めることができる。

・パラメータが大きければ大きいほど、敵を倒せる種類が増える&&初期値が大きいので、最後の敵を倒す戦闘回数が少なくなる。
明らかに小さいパラメータを選ぶと、必要な戦闘回数は増えるので、単調性がある。パラーメタに関しても二分探索で最適な値を探索すれば良い。

・一方で、に関する二分探索の結果がとなる場合は、敵を一人も足せないため、-1
出力すれば良い

感想

回以上の戦闘ってのが厄介すぎる。
回あとに初めてを倒せるようになれば良い。

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

template<class F,class T>
auto  maximize(T imin,T imax,F &f){
    while(imax - imin > 1){
        T mid = imin + (imax - imin)/2;
        if(f(mid)) imin = mid;
        else imax = mid;
    }
    return imin;
}
inline bool solve(){
    int N,M;
    scanf("%d %d",&N,&M);
    if(N + M  == 0) return false;
    vector<int>s(N);
    for(int i = 0; i < N; ++i) scanf("%d",&s[i]);
    auto f = [&](int X){
        int L = 1;
        bool f = false;
        for(int i  = 0; i < M;  ++i){
            if(L + X > s.back() && f ) return false;
            if(L + X > s.back())  f = true;
            auto l = lower_bound(s.begin(), s.end(),L+X);
            auto r = s.begin();
            auto itr = lower_bound(r,l,L);
            int tmp = 1;
            if(*itr < X + L) tmp = max(tmp,X - abs(L - *itr));
            if(itr != s.begin()) tmp = max(tmp,X - abs(L - *prev(itr)));
            L += tmp;
        }
        return true;
    };
    int ans = maximize(0, s.back() + 1,f);
    if(ans + 1 <= s.front()) ans = -1;
    printf("%d\n",ans);
    return true;
}
signed main(){ while(solve()); }