Japan Alumni Group Summer Camp 2015 Day 2 B - 監獄

問題

jag2015summer-day2.contest.atcoder.jp

解法

二分探索をします。

ok(x) = (x 以下の数のうち, N 回目の操作で選ばれる数があるか) という判定をします。この判定ができると, 結局のところ求めたい x というのは ok(x) が true になるような数の中で最小の数, ということになります。これは二分探索でいけそうです。

では ok(x) を求めるプログラムを考えます。

1 回の操作では, x 以下の数のうち, 0 及び K の倍数が消されます。よって, x 以下の数のうち, 残る数の個数は x/K + 1 個減ります。このようにして x 以下の数のうち最大のものが 0 番目以上の数として残れば ok(x) は true です。

int N, K;

bool ok(ll x) {
    for (int i = 0; i < N; i++) {
        if (x >= 0 && i == N-1) return true;
        x -= x/K + 1;
    }
    return false;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> K;
    ll low = -1, high = 1ll<<60;
    while (high - low > 1) {
        ll mid = (low+high) / 2;
        if (ok(mid)) high = mid;
        else low = mid;
    }
    cout << high << endl;
    return 0;
}