Codeforces #176 Div2 B "Pipeline"

問題

http://codeforces.com/contest/287/problem/B

訳

N軒の家に水が流れているパイプ（給水パイプ）を設置したいと考えている。
しかし、今のところ給水パイプは１つだけである。
そこで、いくつかのスプリッターを使って
ちょうどN本の給水パイプを作りたいと思っている。

スプリッターは１つの入水口（これは給水パイプにしか繋ぐ事は出来ない）と
x個の給水口で構成されている。
スプリッターを給水パイプに繋ぐと、全ての給水口から水が流れ出るようになり、
それぞれが給水パイプとなる。（イメージ図）
スプリッターの給水口の形状は一般的なものであり、
そこにさらに別のスプリッターの入水口を差し込む事が出来る。

持っているスプリッターは 2, 3, 4... Kの給水口を持っている。
N個の給水パイプを作るために最低限使わなくてはならないスプリッターの数を返せ。
それが不可能であれば-1を返せ。

制約

1 <= N <= 10^18
2 <= K <= 10^9

考えた事

使う本数で２分探索。
その時の最大限作れる給水パイプがN以上なら
もっと少なくて済む可能性がある。

コーナーケース

うわー！Nが1の時は１個も使わなくてよい！

事後

ちょうどNの作りたいのちょうどの部分を見落としてた。
けど幸いにも見落としててむしろよかったーな部分だった。

ソースコード

typedef long long ll;

int main() {
    ll n, k;
    cin >> n >> k;

    // 1のときは0
    if( n == 1 ){
        cout << 0 << endl;
        return 0;
    }

    // 全て使った時の本数
    ll all = k + (k - 2) * (k - 1) / 2; 

    // 無理な時
    if( all < n ){
        cout << -1 << endl;
        return 0;
    }

    // ２分探索
    int h = static_cast<int>(k - 1);
    int l = 1;
    while( l <= h ){
        int m = (h + l) / 2;          // 試す本数
        ll r = k - m - 1;             // 残りの本数
        ll p = all - r * (r + 1) / 2; // 作れる給水パイプ数
        if( p >= n ){
            h = m - 1;
        }else{
            l = m + 1;
        }
    }

    cout << l << endl;
}