| A | B | C | D | E | F | |
| 問題文 | ■ | ■ | ■ | ■ | ■ | ■ |
| 自分の提出 | ■ | ■ | ■ | ■ | ■ | ■ |
| 結果 | AC | AC | AC | AC | AC | AC |
全体感想
46分、ノーミス全完で、9位でした。ABCコンテストでの自己べ順位を更新しました♪やったぜ。
Fを開きます。細部を詰めるのがちょっと手間っぽいですが、大体の方針はすぐに立ちました。集中して、21分で解ききります。FAとか取れていないかな？とか調子のよいことを考えましたが、FAは10分台ですし、何なら6完最速が20分台です。きびしー。
最近、易化が続いていたように感じていましたが、今回はDEFどれも解きごたえがあって、ちょうど楽しいABCと感じる難易度でした。
問題C – Next Prime
エラトステネスの篩による、素数表の構築を紹介します。（本問では必要ないです）
・is_prime[n]：n が素数かどうか
・primes[n]：n 番目の素数（0-indexed）
atcoder だと、$10^6$ くらいまでの前計算で足りることがほとんどという印象です。$10^9$ クラスになると、6x + 1 や 6x + 5だけに興味を持つことで空間計算量を減らすことなども有益になってきそうですが、私は対策していないです。
問題D – Prediction and Restriction
条件が、「$K$ 手前」にしかかかってきていないので、$K$ で割った余りごとに問題を分割して考えます（最近だと、★ABC147-F★でも似た考え方が登場しました）。「直前と同じ手を続けて出せない」ゲーム $K$ 個に帰着されます。
例えば、グーを最後に出したときの最適スコアについて考えましょう。これを知りたければ、直前に出した手で場合分けをして、「直前に出した手がチョキだった場合の最適スコア」「直前に出した手がチョキだった場合の最適スコア」が分かれば良さそうです。したがって、（最終手ごとの最適スコア）を更新していく形の dp を考えることができます。
問題E – Handshake
・「価値 $x$ より大きい握手を全て選んでいる」
・「ちょうど価値 $x$ の握手はいくつか選んで、ちょうど $M$ 通りになるようにしている」
FFT（高速フーリエ変換）による解法
「何らかの基準を設けてまとめて計算しなければいけない」と書いたわけですが、本問題では$A_{\max}$ が小さいので、「握手の価値ごとにまとめる」ことが可能です。
そのためには、各 $x$ に対して、$A_i + A_j = x$ となる $(i,j)$ が数えられればよいです。和ごとの件数を気にしているので、データの持ち方も変えます。
$f_n = \text{($A_i = n$ となる $i$ の個数)}$ としてみます。このとき、$A_i + A_j = x$ となる $(i,j)$ の組の個数は、$\sum_{n + m = x} f_nf_m$ で表されます。
・これは数列 $f$ と $f$ の畳み込みと呼ばれる操作です。
・あるいは、$f(x) = \sum_{n=0}^{\infty} f_nx^n$ としたとき、多項式の積 $f^2$ の係数です。
$A$ 項の数列の畳み込み、あるいは $A$ 次以下の多項式の積は、高速フーリエ変換を上手く利用することにより $\Theta(A\log A)$ で計算できます。
高速フーリエ変換による多項式乗算：成り立つことの概要
- 多項式 $f, g$ があるとする。$h = fg$（多項式の積）とする。これを求めたい。
- $\deg f + \deg g < L$ となる $L$ をとる。
- 「長さ $L$ でのフーリエ変換」という変換があり、これは多項式を、長さ $L$ の数列にうつる。$f,g$ のフーリエ変換を $\mathcal{F}f, \mathcal{F}g$ とする（※ $L$ を指定して初めて変換が定まります）。
- 「畳み込み定理」：$\mathcal{F}h = \mathcal{F}f * \mathcal{F}g$ が成り立つ（任意の $i$ に対して $\mathcal{F}h[i] = \mathcal{F}f[i] * \mathcal{F}g[i]$）。
- 各点積の計算は当然 $O(L)$。したがって、フーリエ変換 $\mathcal{F}$ およびその逆変換 $\mathcal{F}^{-1}$ が高速に計算できれば、畳み込みの計算が高速に行える。
- 高速フーリエ変換 (FFT / Fast Fourier Transform) というアルゴリズムが存在して、適切な条件下で $\mathcal{F}$, $\mathcal{F}^{-1}$ が高速（$\Theta(L\log L)$）に計算できる。例えば
- 係数体が $\mathbb{C}$ で、$L = 2^n$。
（※ $2$ べきである必要はない。小さな素数の積なら高速） - 係数体が $\mathbb{F}_p$ で、$L = 2^n$。$p-1$ が $2^n$ の倍数。（$p = 998244353$ など）
※ 数論変換 (NTT / Number Theoretic Transform)といって、FFTと呼び分ける流儀もあります。
- 係数体が $\mathbb{C}$ で、$L = 2^n$。
※ 基本的に $L = 2^n$ ととれば大丈夫。
※ $\deg f, \deg g < L$ ではなく、$\deg f + \deg g < L$なので注意。小さい $L$ だと別のものが計算されてしまいます（そちらにも応用上の利点は存在し得ますが）。
※ 勉強する際は、「畳み込み定理」（フーリエ変換により畳み込みが各点積に化ける理由）と、「高速フーリエ変換」（フーリエ変換が高速に行える理由）という 2 つの問題を切り分けて学ぶと良いと思います。
詳細は、★ATC 001-C：高速フーリエ変換★などを参照してください。
AtCoder + Pythonの条件下で、FFTはnumpyから利用できます。上に述べた程度のことを理解しておけば、「フーリエ変換」の定義や「高速フーリエ変換」の中身について詳細が分からなくとも、畳み込みの計算の活用できるはずです。
※ 現AtCoder環境では、低レベル処理の整備よりも問題の考察に学習の比重をおけることがPythonの利点の1つになると思います。遠慮せず使っていきましょう。
※ 上でいう $L$ を指定しないととても遅くなることがあります。
※ numpy.fft は、複素数体 $\mathbb{C}$ での計算を利用します。実部、虚部に64bit 浮動小数を用いるため、だいたい 53bit 程度の計算精度しか保証されません。積の係数の大きさが巨大になる場合には、例えば $f(x) = 2^{15}f_1(x) + f_2(x)$ といった要領で、係数の小さな多項式の乗算に分割して扱う方法があります。
ATC 001-C の提出例：■
ATC 001-C の提出例：■ （最近自作したNTT。わりと雑かも。）
今回のABC-E の提出例：■
問題F – Surrounded Nodes
「2方向以上の部分木が黒点を含む」「自分自身は白点」
実際には、「黒点を含む確率」よりも「黒点を含まない確率」の方が扱いやすいです（$(1/2)^n$ で求められるため）。例えば部分木が3つあり、黒点を含まない確率が $p_1,p_2,p_3$ とします。
