このシリーズの目的
知識と少しの工夫で解ける高得点問題(ABCのG問題など)が上位勢のみに解かれている現状は、望ましくありません。
これらの問題は、発想自体は単純であるのにも関わらず、実装から考察の意図が読み取りにくいため、多くの低レートコーダーが挑戦できずにいます。
本シリーズは、その障壁を下げ、より多くの人がこれらの問題に取り組めるようにすることを目的としています。
尚、筆者は茶色コーダーです。同じ目線で話せることを引き換えに、引き出しは限られていることをご了承ください。
対象読者
- 早解きのみでperfの最大化を狙っている茶色以上のコーダー
- 自身の潜在性を過小評価している茶色以上のコーダー
- 数分で新しいアルゴリズムを知りたい貪欲な茶色以上のコーダー
参考文献
詳細な説明はこれらの記事の方が有用です。
目次
・このシリーズの目的
・参考文献
・高度典型とは
・形式的べき級数とは
・おわりに
高度典型とは
問題解決において、「使える武器」を増やさないことには、発想の実現性を検証できないために、質の高い考察ができません。
故に、幅広い問題に対して有効なアルゴリズムや考察方法を「典型」と呼び、その習得が、実力以上の問題攻略の要とされています。
ここで言う「高度」とは、実装時にクラスなどを用いて構造を整理しなければ扱えないほど、処理や手順が複雑なことを指します。ただし、複雑だからといって、使える場面が限定的というわけではありません。
高度典型と呼ばれるものは、以下のようなものが挙げられます。
- 形式的べき級数
- セグメント木
- 行列累乗
- ネットワークフロー
今回は「形式的べき級数」を解説します。
触れること
- 競技プログラミングの文脈における形式的べき級数の意味
- 用途と実装の手順と各工程の意味の解説
- 関連用語の紹介
触れないこと
- 畳み込みの高速演算方法
- 細かな合成テクニック
- 問題・実装例
形式的べき級数とは
組み合わせの数を調べるための計算手法に関わる配列を、構築・運用する上で理解する必要のある概念です。具体的には、項が無限個存在しうる多項式を指します。略してFPS若しくは母関数とも呼ばれます。
数学的な概念としては、新しいものばかりなので、難しく感じられるかもしれませんが、端的にいうと、「ルールに沿った集合の合成処理を表現可能である」性質が評価されています！
実装手順は以下の通りです。
- 求める値の単位を決める
- 単位に即した要素/操作を母関数に落としてみる
- 合成処理を調整するために、重みの関数を定義付ける
- 次数が$0$から$N$までの係数を配列に順番に入れる
- 母関数を任意の方法で合成して、できた関数の$N$番目の係数を抽出する(これが求めたい答え！）
今から、Q&Aの形式で疑問を解消していきます。
Q1. 組み合わせの数って何？
目標の値を作るにあたって、いろんな要素(=集合)から選べる(=組み合わせ)ときに、可能な通り数のことです。
組み合わせる条件が単調であれば、写像12相の中から公式を使えば求まりますが、条件が複雑化すると、人の手に追えないため、自動演算のアルゴリズムに任せます。我々はルールを決めるだけで済みます。
Q2. 多項式とは？
変数が含まれている式のことです。多項式では、定数も、係数付きの$x^0$だと見なされます。
Q3. 母関数とは？
$x^0$から$x^\infty$まで、全ての要素を含んだ関数のことです。数学的には
$$
A(x) = \sum_{i=0}^{\infty}w(i)a^ix^i
$$
と表現されます。
ここで、$a^i$は係数を、$W(i)$は重み付き関数を表します。($a^i=0$もあり得ます)。
母関数、任意の$A(k)$を高速に求めるものでなく、あくまで、係数を抽出するためにあります。
つまり、「構築や合成を表現するための記号的な道具」にすぎません。多項式という形式はあくまで便宜上のものであり、その数学的な意味は重視されません。
目標値を$N$としたとき、その組み合わせの数は係数$a_N$になるように初期化・合成されていきます。
Q4. 非交和とは？直積とは？
集合の合成のルールのことです。
説明のために、集合を表す母関数の$A$と$B$を用意します。合成後の母関数を$C$、各関数の次数$i$の係数を$a_i$,$b_i$,$c_i$と表現します。
非交和は、$A$と$B$のいずれかから、要素を取り上げるルールを指します。
場合の数では「または」のことで、直感的な方です。
母関数上での合成では、$c_k=a_k+b_k$と表現されます。これはただの足し合わせなので、わざわざ級数で表現する必要はありません。DPとかの別解があります。
対して、直積は、$A$と$B$から独立に選んだ要素から、新しい要素を作るルールを指します。
場合の数では「かつ」のことです。
これは畳み込みと呼ばれる演算で、二つの多項式を合成し、係数$c_k$を「$A$から$i$、$B$から$k-i$を選んで作れるすべての組み合わせの合計」として計算します。
この処理はとても複雑なので、高速化されたライブラリを使わないと$O(N\log{N})$で済みません。
Q5. 合成する集合はどこにあるの？
求めたい値が組み合わせで決まるときに、それを構成する情報が必ず与えられていると思います。各要素を適切な集合に表現しなおすことで、合成処理が書けるようになります。つまり、母関数は、与えられた情報から自分で作る必要があります。
気遅れする必要はありません。
例えば、$N$の倍数のみを保有する母関数を作りたければ、$i\mod N=0$となる次数のみに係数$1$を付与し、他を$0$で補完すれば完成です。
また、操作が無限回できて、各操作の選択肢が固定のときには、一つの操作パターンを関数$A(x)$で表した後に、繰り返しを表す$SEQ(x)=\frac{1}{1-A(x)}$の関数と合成した後に、級数展開をすれば、回数無制限の操作を含む母関数を楽に正確に設計できます。
同様に、上記の例に該当しない場合も、全体を構造に分解して考えて構築できれば、あとは合成するだけで簡単に作れます。
Q6. 重み付き関数ってなに？
Q3で紹介されていた式の内の$w(i)$のことです。
畳み込みの処理に一工夫を加える時に導入します！
関数を合成するときに、一般的に係数は足し合わせられるだけですが、直積の条件によっては、それに留まりません。
例えば、係数$a_i$, $b_j$に対して、$c_{i+j}=\frac{(i+j)!}{i!j!}a_ib_j$を取ることがあります。その時、畳み込みの実装自体に介入することは、高速化の都合上できない為、代わりに、次数を受け取って定数を返す関数を設計して、母関数を表す配列の初期化の際の数値代入時に都度定数倍を適用することで解消します！
つまるところ、この重み付き関数こそが、形式的べき級数を用いた組み合わせ問題攻略の汎用性の正体です！
おわりに
形式的べき級数は一見難解に見えますが、考え方自体は十分に実践可能な範囲です。
本記事が、その仕組みを理解し挑戦するきっかけになれば幸いです。
ぜひ参考文献の方に目を通してみてください。踏襲できていない要素が補完されているので、より体系的な理解へとつながります。
ここまで読んでくださり、ありがとうございました。
お願い
語弊などがたくさん含まれていることを懸念しています。下手な言い回しなどを含めて、修正すべき箇所を列挙したPRなどを送ってくださると、とても報われます。よろしくお願いします。