yoshiki_utakata https://blog.hatena.ne.jp/yoshiki_utakata/ 猫でもわかるWeb開発・プログラミング https://www.utakata.work/ はじめに どうも、yoshikyotoです。 本番で頑張って実装した高速フーリエ変換、ちょっと直したら通ったので貼っておきます。 問題: http://atc001.contest.atcoder.jp/tasks/fft_c 間違っていた点 2の冪乗とは、2, 4, 8, 16, ... のことであるが、2の冪乗ではなく、1つ前の数字の2乗を求めていた（2, 4, 16, 256, ...）ため、数字が大きくなりすぎてTLEしていた 最終的に real() の切り捨てを出力していたが、そこの誤差で死んでいた？四捨五入にしたら通った。ここはよく分かっていないので要復習 実装 本当はJavaで実… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fwww.utakata.work%2Fentry%2F2015%2F06%2F07%2F195042" title="AtCoder Typical Contest #001 C - 高速フーリエ変換 を解いた - 猫でもわかるWeb開発・プログラミング" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2015-06-07 19:50:42 rich https://www.utakata.work/entry/2015/06/07/195042 1.0 100%