読者です 読者をやめる 読者になる 読者になる

yukicoder ★★★ No.413 +5,000,000pts

問題

No.413 +5,000,000pts - yukicoder

考察

一風変わった問題ですね。
Hackできるケースを考える問題のようです。

与えられたコードを読むと、いかにもな解の公式が書かれています。
+側しか取っていませんが、tは最大の整数なので問題なさそうです。

全く分からないので解説を見ました。
すぐ解説を参照できる、なんて便利なのでしょうか。
テストケースも見れますし、POJもこうなってくれればなぁ……。

yukicoder

sqrtに与える箇所で誤差が生じ、結果が異なってしまうようです。
C++のdoubleはlong longと同じ64bitで表されますが、実際仮数部は52bitしか使われないため、ここで表現できる値が変わってきます。

 2^{63} = 9.2 * 10^{18}

 2^{53} = 9.0 * 10^{15}

さて、結果が変わってしまうような状況を考えます。
今回はtの値を求めるわけですが、 t^{2} + t = dとなるギリギリの状況が結果をずらしやすそうです。
丸め誤差により、1.99999...という小数があると、小数点以下16桁目くらいで丸められ2.0になってしまいます。
本来のtより大きく出てしまうのでこれは誤りとなり題意を満たします。

そのため、ギリギリの状況で生まれたdから1を引けば、このような値が作れます。
もちろん小さい値では発生しないため、 1 + 4 * dが16桁を超えるような値にしてあげます。

最後に t~{2} + t = dとなるtを考えます。
解の公式で結果が整数になれば良いので、 -1 + sqrt(1 + 4 * d)が偶数になればよいです。
そのために、 sqrt(1 + 4 * d)が奇数(正の整数)とします。

 sqrt(1 + 4 * d) = 2k + 1として変形をし、 d = k^{2} + kが成り立ちますので、-1したdを適当な個数出力すればOKです。

コード

int main() {
    int count = (int) (1e5) + 10;
    for(ll i = (ll)(1e8); count >= 0; i++, count--) {
        ll d = i * i + i;
        cout << d - 1 << endl;
    }
    return 0;
}

備考

タイトルが面白いです。
何度でもHackできるコンテストがあったらこんな事になってしまうのでしょうか。

答えのコードが極めて短く、解説の行数が何だったのかという感じですが、なんとなくTopcoderらしい問題だなぁと思いました。
題材が環境/言語依存ではありますが、とても良い問題だと思います。