yukicoder No.413 +5,000,000pts

余談
サンプル出力の数がどうみても日付なのだけど、何なのかわからず気になっているので、わかる方がいましたら教えてください

（※以下は試行錯誤により解く過程を記したものです。ちゃんとした解説が読みたい方はeditorialを読んでください）
calc関数は、二次不等式t*t+t≦dを解の公式を用いて解いているので、誤差が発生しなければ正しい値を返すはず。
ということは、バグるのは誤差が発生するとき。
doubleからlong longへの変換のときの丸めが怪しそうだなと思ったので、実数の範囲での最大値がほぼ整数となるようなものであって、誤差が発生しような大きめのdについて調べてみる

#define ll long long
ll calc(ll d) {
  return (ll)((-1 + sqrt(1 + 4*d)) / 2.0);
}
int main(){
	for(ll M=1e8;M>1e8-100;M--)for(int i=-100;i<100;i++){
		//t*t+t<=dの実数の範囲での解の最大値が整数になるのは
		//dがある整数Mを用いてM*M+Mとあらわされるとき（不等式から明らか）
		ll d=M*M+M+i;
		ll ans=calc(d);
		if(ans*ans+ans>d||(ans+1)*(ans+1)+(ans+1)<=d)printf("%lld %d %d\n",M,i);
	}
	return 0;
}

これを実行してみると

100000000 -1 100000000
99999999 -1 99999999
99999998 -1 99999998
中略
99999903 -1 99999903
99999902 -1 99999902
99999901 -1 99999901

という出力が得られた。どうやらdがM*M+M-1という形で書けるときのようだ。
このときt*t+t≦dの実数の範囲での解の最大値はMよりもわずかに小さくなるので、正しい答えはM-1となるはずだが、calc関数はMを返してしまっている。

ということでM*M+M-1のような形で書ける大きな数を10万個生成する

int main(){
	long M;
	for(M=100000000;M>99900000;M--)printf("%ld\n",M*M+M-1);
	return 0;
}

これでめでたくACを得たが、解説を読むと、どうやら問題はdoubleからlong longへの変換ではなく、sqrt関数へ渡すためのlong longからdoubleの変換の方だったらしい。
doubleの精度は53bitなので、64bit整数の値を保持できるとは限らないことが問題の本質だったそうだ。

それはさておき短縮。
とくに工夫する要素はない

i=999e5;main(){for(;i++<1e8;)printf("%ld\n",~-i+1L*i*i);}

57B

メモ

yukicoderでゆるふわgolf

yukicoder No.413 +5,000,000pts