【AOJ】AOJ 2826 - ゲームバランス

模擬国内2017D

問題のリンク

解説

単調性があるため、 で二分探索をする。

を決め打ったときに、最小で何体モンスターを倒す必要があるか求めることができれば、それが 以上かを判定することで解くことができる。

倒すための最小のモンスター数について求める方法を解説する。

レベルが高くなると、倒すことができるモンスターの集合は単調に大きくなっていくため、同じモンスターをレベル とレベル のときに倒して、後者の方が戦闘後のレベルが高い（か等しい）ことを示せれば、貪欲にレベルを上げられるだけ上げて良いと示すことができる。

（後述するが、今倒すことができるモンスターの中で最もレベルが上がるモンスターを求めることは比較的容易にできる。）

どちらのレベルでも倒せるモンスターについて、その強さを とおく。

(1) のとき

は に、 は になる。

それぞれの最大値がどの組合せになるかで場合分けし、いずれの場合も のほうが戦闘後のレベルが小さくならないことを示す。

と のとき

自明。

と のとき

このようなことはない。（ であるため であるが、そのときは になるため。）

と のとき

となっているのでOK。

と のとき

等しい。

(2) のとき

は に、 は になる。

と のとき

自明。

と のとき

より、

より、

よりOK。

と のとき

だから

ここで だから、

よりOK。

と のとき

よりOK。

(3) のとき

は に、 は になる。

と のとき

自明。

と のとき

を最後に使うと、

よりOK。

と のとき

を最後に使うと、

よりOK。

と のとき

よりOK。

以上より、貪欲にレベルを上げられるだけ上げて良いことが分かった。

次に、現在のレベルが のときに、どのモンスターを倒せば最もレベルが上がるかについて考える。（なお、最後のモンスターを倒せるときには倒す）

倒すモンスターの強さを とする。

(1) のとき

になるため、 はなるべく小さくなるように選べば良い。

(2) のとき

になるため、 はなるべく大きくなるように選べば良い。

よって 以上で最小のモンスターと、 以下で最大のモンスターが候補になるので、これらを実際に試せば良い。

実装について

二分探索では、倒す回数が 回以上となる最小の を求めるため、 の区間と対応する結果としては、 絶対にクリアできない | M回以上かかってクリア | M回未満でクリア となる。

二分探索の中では、(1)ボスを倒せるか判定→(2)倒す候補について調べる→(3)どれも倒せなかったらクリアできない=無限回かかるとする→(4)レベル更新

を繰り返している。

最後に求めた ok が条件を満たすか確認する。クリアできない場合と、 回未満でクリアしてしまう場合がある。

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

#define REP(i, n) for (int i = 0; i < (n); i++)

void solve(int N, int M) {
    vector<long long> s(N);
    REP(i, N) cin >> s[i];
    auto check = [&](long long X) -> long long {
        long long curlev = 1, count = 0;
        while (true) {
            count++;
            if (curlev + X > s.back()) {
                break;
            }
            long long nextlev = curlev;
            int i = lower_bound(s.begin(), s.end(), curlev) - s.begin();
            for (int j = i - 1; j <= i + 1; j++) {
                if (0 <= j and j < N and curlev + X > s[j]) {
                    nextlev = max(nextlev, curlev + max(1LL, X - abs(s[j] - curlev)));
                }
            }
            if (curlev == nextlev) {
                count = 2000000;
                break;
            }
            curlev = nextlev;
        }
        return count;
    };
    long long ng = 2000000, ok = 1;
    while (ng - ok > 1) {
        long long md = (ok + ng) >> 1;
        if (check(md) >= M) {
            ok = md;
        } else {
            ng = md;
        }
    }
    long long res = check(ok);
    if (res != 2000000 and res >= M) {
        cout << ok << '\n';
    } else {
        cout << -1 << '\n';
    }
    return;
}

int main() {
    int N, M;
    while (cin >> N >> M, !(N == 0 and M == 0)) solve(N, M);
    return 0;
}