2023年10月中旬くらいからAtCoderの「競プロ典型90問」に取り組んできました。最初は001番から順番通りに解いていこうと思ったのですが、難易度が高い問題に当たるとなかなか進めなくなるので、まずは★2つの問題、そして★3つの問題と難易度の低い問題から解いていくことにしました。
★6つの問題まで解き終わり、現在は、難易度の一番高い★7つ問題に取り組んでいるのですが、難しすぎて、まず自分で解けるということはありません(自分の場合は)。公式解説や想定ソースコードを読みながら、理解をしようと思うのですが、 それだけでは理解できないこともほとんどです。
本問は高速フーリエ変換(FFT)を用いた畳み込みを使うと、全体計算量で解くことができ、FFTの知識がなくても
ACLのatcoder::convolution関数を使うと解くことができるとのことでしたが、学生時代から、いつかはちゃんとFFTを理解したいとの思いもあったので、まずは『アルゴリズムC 第3巻』を読みながらFFTを理解するところからはじめました。
『アルゴリズムC 第3巻』の「41 高速フーリエ変換」をPythonで - Mae向きなブログ
ここまでで、FFTについては、理解が進んだような気がしたのですが、FFTと剰余との関係がよくわかりませんでした。両者の関係を丁寧に説明してあるのが、参考サイトでした。FFTとNTTの関係がわかりやすく説明されており、さらに
C++のサンプルプログラムもあり大変参考になりました。- NTT(数論変換)を使って2つの多項式の積を求めるプログラム - Mae向きなブログ
