[AtCoder 参加感想] 2019/12/29:ABC 149

  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

なんか、同じ人間の間で異なる手同士の握手が交わされたりして、しばらく混乱します。制約の $M$ の部分から、$N^2$ 通りから上位 $M$ 件を選ぶ問題だと思考が整理できて落ち着きを取り戻します。
$N^2$ 通りということで、イメージとしては、$N\times N$ の表、次の問題が思い出されました。
発想としてですが、$O(N^2)$ 件の和取り扱わなければいけないので、上位から順に生成していくような方法は絶望的です。「何らかの基準を設けてまとめて計算しなければいけない」というのが根本にあって、そこから発想を広げていきます。
「左手の握手先」ごとに和をまとめることを考えます。それぞれの左手に対して、対となる右手は、価値が高い方から順に選べばよいです。いくつの右手を選ぶかを求められれば良さそうです。
これを求めるために、最適解の構造を観察します。最適解では $N^2$ 通りの握手から価値の高い上位の握手を選んでいきます。これは、ある $x$ に対して、

・「価値 $x$ より大きい握手を全て選んでいる」
・「ちょうど価値 $x$ の握手はいくつか選んで、ちょうど $M$ 通りになるようにしている」
という状態です。左手ごとに、価値 $x$ 以上の握手の件数を手に入れることは、ソートと二分探索による基本的な手法です。これと $x$ に対する二分探索を組み合わせることで、境界となる $x$ を、$\Theta(N\log N\log A_{\mathrm{max}})$ で求めることができます(左手ごとの握手の件数の一覧を手に入れるときに、尺取りを使って改善することもできます)。

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と呼び分ける流儀もあります。

※ 基本的に $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方向以上の部分木が黒点を含む」「自分自身は白点」
の2条件と言い換えられる。自身が白になる確率は 1/2 でこれは簡単。
・「2方向以上の部分木が黒点を含む確率」
を計算するために必要なデータを考える。どの部分木に入っているかだけが重要で、黒点の場所は見なくてよい。よって、木の形の詳細は要らない。より詳しくは、「部分木ごとの頂点の個数」があれば、確率が決まるはず。
◆部分木ごとの頂点の個数を求める
典型的な 木dp です。根付き木でdpすると、子側の部分木サイズが分かります。親側は全頂点数からの引き算で求まります。
◆部分木ごとの頂点数から、「2方向以上の部分木が黒点を含む確率」を求める
部分木について最終的に注目するのは、黒点を含むかどうかだけです。よって、まず、黒点を含むかどうかの確率を求めておきます。
また、「2方向以上」をどうするかですが、「2方向・3方向・4方向・…の場合」と考えるよりも、全体から「0方向の場合」「1方向の場合」を除く方が簡潔です。

実際には、「黒点を含む確率」よりも「黒点を含まない確率」の方が扱いやすいです($(1/2)^n$ で求められるため)。例えば部分木が3つあり、黒点を含まない確率が $p_1,p_2,p_3$ とします。
・黒点を含む部分木がない確率:$p_1p_2p_3$.
・部分木1のみが黒点を含む確率:$(1-p_1)p_2p_3$.
・部分木2のみが黒点を含む確率:$p_1(1-p_2)p_3$.
・部分木3のみが黒点を含む確率:$p_1p_2(1-p_3)$.
を足せばよいです。$N$ 個の積を $N$ 件計算しようとすると計算量が悪くなりますが、これらの和を \[p_1p_2p_3\times \biggl(1 + \biggl(\frac{1}{p_1}-1\biggr) + \biggl(\frac{1}{p_2}-1\biggr) + \biggl(\frac{1}{p_3}-1\biggr)\biggr)\] のように計算してあげることで、隣接頂点数の個数関して線形時間で計算できます。
問題Eに続き、方針が分かったあとも、管理しなければいけない情報量が多めで、細部をしっかり詰めて正確にやりきる力もかなり問われていると思います。

タイトルとURLをコピーしました