ABC056C Go Home

C - Go Home
ACコード
https://atcoder.jp/contests/abc056/submissions/8498356

int main()
{
	cout <<setprecision(10);
	ll x ; cin >> x;
	
	ll ans = 0 ;
	ll sum = 0;
	for(ll i = 0 ; i < x ; i++){
		sum += i;
		if(sum >= x){
			ans = i ;
			cout << ans << endl;
			return 0;
		}
	}
	ans = x;
	cout << ans << endl;
			
}

解法
①sum に1 ,2,...と足していって、 xを超えたときを考える、
最後に足した値をnとすると、1個前に足した値はn-1、
nを足す前のsumは x-1 以下なので、
nを足した後のsum は x + n より小さい。
よって 1 ~ (n-1) までのどれか(k)を sum から引く（この操作は、時刻 k - 1からkにかけての操作を 「飛ばない」にすることである）ことでちょうどXに飛ぶことが出来る。

解法②　（解説の解答）
①の場合より計算量を落とす方法
①のノリで、ピョンピョンカンガルーさんがどんどん跳ねたとき、sum = 1 + 2+ ...+n (nを足したらxを超える）
この時X <= 1/2 * n *(n+1)
式変形をして
n ^ 2 + n -2X = 0
となるのは二次方程式の解の公式のノリで
n = -1/2 + root(1+8X)/2
このときのnが答えになる（多分）

• >ならなかった 解法②で解くのどうやるの？俺は知らん

ちなみに書いたコードは↓

int main()
{
	cout <<setprecision(10);
	ll x ; cin >> x;

	ll n = (-1 + sqrt(1+8*x)) / 2;
	cout << n << endl;
}