D. Sand Fortress | Educational Codeforces Round 44
構成のベースは以下の2通り。 適切な最大の高さ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; }