D. Sand Fortress | Educational Codeforces Round 44

構成のベースは以下の２通り。 適切な最大の高さxは二分探索で求める。この通りに構成したときに、余りが出る場合があるが、x以下のすべての高さが存在するので、余りをrとするとceil(r/x)個だけ同じ高さの横に挿入すればいい。

// Hが大きすぎても無意味なので適当な値で制限
const ll LIM = 3000000000ll;

ll N, H;
cin >> N >> H;

if (H > LIM || N < H*(H + 1) / 2) {
    H = LIM;
    ll L = 0, R = H + 1;
    while (R - L > 1) {
        ll mid = (L + R) / 2;
        ll use = mid * (mid + 1) / 2;
        if (use <= N)L = mid;
        else R = mid;
    }
    ll re = L + (N - L*(L + 1) / 2 + L - 1) / L;
    cout << re << endl;
} else {
    ll L = H, R = LIM + 1;
    while (R - L > 1) {
        ll mid = (L + R) / 2;
        ll use = mid * (mid + 1) / 2 + (H + mid - 1)*(mid - H) / 2;
        if (use <= N)L = mid;
        else R = mid;
    }
    ll use = L * (L + 1) / 2 + (H + L - 1)*(L - H) / 2;
    ll re = 2 * L - H + (N - use + L - 1) / L;
    cout << re << endl;
}