高速フーリエ変換(FFT)というテクニックを使って掛け算をしました． 問題：http://www.spoj.pl/problems/MUL/ コード：https://gist.github.com/854921 再帰してるせいか結構遅い．Spaghetti SourceにあるFFTが速いという噂なので気が向いたら試してみたいで…

寝起きにぼけっと考えていた． 縦 | 横 に切ると，再び長方形になる． dp[y][x]や，dp[line][y]といったタイプの動的計画法に帰着しやすい． 面積=縦×横． 各マスに数字を書いたとき，その部分長方形の総和を，下準備O(W*H)の後でO(1)で求められる． さらに…

深夜，唐突にフラクタルっぽいものを生成したくなったので勢いで描いてみました． マンデルブロって何? カオスな図形として良く取り上げられるので見たことある人は結構いるんじゃないかとは思いますがとりあえず． Wikipediaによると とあります．これだけ…

問題 空間に個の点がある．点から2つの点を選び，2点間のマンハッタン距離を最大化したい． ただし，マンハッタン距離とは，2点に対して で与えられる距離のことである． 単純に全通り試すとだけの計算量がかかるが，が大きいと計算コストがかなり大きくなる…