AtCoder ARC 109 B - log (茶色, 400 点)

二分探索でやればよさそう。本当は でもできるのかも。

• 問題へのリンク

問題概要

正の整数 が与えられる。

整数 のうち、いくつか選んだものが以下の条件を満たすようにしたい。そのような選び方のうち、選ぶ個数の最小値を求めよ。

• 選んだ整数はいくつかの正の整数の和に分割させることができる
• 分割して得られた整数の中に がすべて登場する

制約

• 

考えたこと

を に分割させるのがよい。よって、

を満たす最大の を求めると、 が答えになる。そのような は二分探索法で求められる。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    long long N;
    cin >> N;
    long long left = 0, right = 2000000000;
    while (right - left > 1) {
        long long x = (left + right) / 2;
        if (x * (x+1) / 2 <= N+1) left = x;
        else right = x;
    }
    cout << N + 1 - left << endl;
}