ICPC模擬国内2017D : ゲームバランス

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2826&lang=jp

問題

種類のモンスターが昇順に与えられる。
主人公はレベル1からスタートし、自分のレベル+未満の敵を倒すことが出来る。
敵を倒すとだけレベルが上昇する。
このゲームでは、番目の敵を倒すとゲームクリアとなる。
主人公が出来るだけ少ない戦闘回数でクリアするようにプレイしたとき、戦闘回数が回以上になるようにパラメータを求めよ。

解法

とクリアに必要な戦闘回数を適当にグラフにしてみると単調なことがわかります。これは、が増えたからと言って戦闘回数が増える訳ではないことから明らかです。
単調性を確認できたので、を2分探索することを考えます。
以下、判定部分に関して考えていきます。
効率の良いモンスターの狩り方は、自分のレベルに近いものを狩るのが良いです。このようなモンスターを高速に求めるには、lower_boundして、得られたインデックスとその次のインデックスを見れば良いです。
レベルごとにインデックスを求めておくとより高速ですが、制約が8秒と長いので今回はサボりました。
また、初手で積む場合は、1匹目のモンスターさえも狩れないときです。このときはNGを返せば良いです。

以上、考察でした。案外簡単目ですが、実装で沼ることが多いので注意です。(1敗)

実装

2分探索です。通るときは通りますが、バグるときはバグります。
という訳で判定関数の判定結果と、範囲の動き方をしっかりと確認しておきます。(コード書いてるとだんだんわからなくなってくるので)
縦軸が、戦闘回数、midが現在のです。

戦闘回数がm回以上の時です。最大にしたいので左側をmidに動かして、より大きなについて調べます。

戦闘回数がm回未満の時です。これ以上を大きくしても仕方がないので右側をmidに動かして、より小さなについて調べます。

今回、クリア不可能なときは戦闘回数をINFとして、より大きなを調べています。(クリア出来ないときはが小さすぎるので)
また、最後に求めたがvalidかどうかの確認もしています。これは、求めたが下限や上限になってしまい条件を満たさない時を排除するためです。

コード

提出です。
AIZU ONLINE JUDGE: Code Review

vector<int> s;

int n, m;

const int INF = 1e7;


int check(int X) {
    int count = 0;
    int L = 1;

    //初手詰み
    if (s[0] >= 1 + X) {
        return INF;
    }

    while (L + X <= s[n - 1]) {
        //敵1と敵2のインデックス
        int e1 = lower_bound(s.begin(), s.end(), L) - s.begin();
        int e2 = e1 - 1;

        //out of indexでない かつ 倒せるならdiffを更新
        int diff = 1;
        if (e1 >= 0 && e1 <= n - 1 && s[e1] < L + X) {
            diff = max(diff, X - abs(L - s[e1]));
        }
        if (e2 >= 0 && e2 <= n - 1 && s[e2] < L + X) {
            diff = max(diff, X - abs(L - s[e2]));
        }
        count++;
        L += diff;
    }

    //ボスへのラストヒットを忘れない
    count++;
    return count;
}


int binary_search() {
    int left = 0;
    int right = INF + 1;
    while (right - left > 1) {
        int mid = (left + right) / 2;

        if (check(mid) >= m) {
            left = mid;
        }
        else {
            right = mid;
        }
    }

    return left;
}


void solve() {
    s.assign(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }

    //クリア不可能でないならok
    int ans = binary_search();
    if (check(ans) != INF) {
        cout << ans << endl;
    }
    else {
        cout << -1 << endl;
    }
}


int main() {
    while (1) {
        cin >> n >> m;
        if (n == 0 && m == 0) break;
        solve();
    }
}