yukicoder 1962 の解説の解説の解説

yukicoder 1962の解説の解説 - メモ
これが読みづらいということではないのですが、最初読んだ時意味が分からず自分で考えてみたら納得できた、ということがあったので、その過程を書いておきます。

以下色々なものを未定義なまま書き進めます。

正規表現とか

突然ですが、正規表現と形式的冪級数を同一視します。以下のように対応関係を定めます。

正規表現 x は形式的冪級数 x に対応する。
正規表現 R と S について、R|S を R または S にマッチする正規表現とし、形式的冪級数 R + S に対応させる。
正規表現 R と S について、RS を R にマッチする文字列と S にマッチする文字列の連結にマッチする正規表現とし、形式的冪級数 RS に対応させる。
正規表現 R について、R* を R の 0 個以上の連結にマッチする正規表現とし、形式的冪級数 1/(1-R) に対応させる。
正規表現 R について、R+ を R の 1 個以上の連結にマッチする正規表現とし、形式的冪級数 R/(1-R) に対応させる。
正規表現 R について、R? を R の 0 個または 1 個の連結にマッチする正規表現とし、形式的冪級数 1+R に対応させる。

この対応関係では、たとえば x と x|x などを区別することに注意してください。前者は形式的冪級数 x に対応しますが後者は 2x に対応します。
(xx...x (x を k 個連結したもの) が何通りの方法で正規表現にマッチするか) = (形式的冪級数における x^k の係数) というのが注目すべき等式です。

ここで、おもむろに a, b を正規表現、A = a+, B = b+ とします。また a, b, A, B に対応する形式的冪級数も a, b, A, B と表記します。
(a|b)+ と (A と B が同じ記号が連続せずに 1 個以上続く) は必ず同じ文字列にマッチします。なぜなら a の繰り返しの部分、b が始まる直前までを A だとみなす、などということができるからです。
つまり、(A と B が同じ記号が連続せずに 1 個以上続く) に対応する形式的冪級数を f(A, B) と表記することにすると、 $\frac{a+b}{1-a-b} = f(A,B)$ が成立するのです。
(A と B が同じ記号が連続せずに 1 個以上続く) はたとえば (A(BA)*B?)|(B(AB)*A?) などと書けるので、形式的冪級数に直すと $f(A,B)=A(1+B)/(1-AB)+B(1+A)/(1-AB)$ とかになるはずです。以上の考察から以下の等式が成り立ちます。

$\displaystyle A = \frac{a}{1-a} = a + a^2 + a^3 + \cdots, B = \frac{b}{1-b} = b + b^2 + b^3 + \cdots$

のとき

$\displaystyle \frac{a+b}{1-a-b} = f(A, B) = \frac{A(1+B)}{1-AB}+\frac{B(1+A)}{1-AB}$

正規表現が 3 つ以上になったとき、同じように (A, B, C, ... が同じ記号が連続せずに 1 個以上続く) に対応する形式的冪級数を f(A, B, C, ...) と表記することにすると、同じように

$\displaystyle \frac{a+b+c+\cdots}{1-a-b-c-\cdots} = f(A, B, C, \ldots)$

が成り立ちます。ここで f(A, B, C) とかを直接書き下す気には全くなりませんし対応する正規表現も手間が多過ぎて書きたくありませんが、ひとまずそれっぽい関係ができました。めでたしめでたし。

逆転の発想

上の議論は、任意の a, b, c, ... およびそれらから定まる A, B, C, ... に対して適用できます。特に a, b, c, ... が何か具体的な正規表現やら「数え上げ的な意味」に対応している必要はないです。また f(A, B, C, ...) も「A, B, C, ... が何らかの繰り返しに対応する形式的冪級数である」のようなことは要求していません。

なので、逆に以下のような等式が言えます。

$\displaystyle a = \frac{A}{1+A}, b = \frac{B}{1+B}, \ldots$

のとき

$\displaystyle \frac{a+b+c+\cdots}{1-a-b-c-\cdots} = f(A, B, C, \ldots)$

前の節で私たちは怠惰ゆえに三変数以上の f を明示的に書くことを避けた訳ですが、わかりやすい形になってくれたのでその必要もなくなりました。めでたし。

一応念のため、yukicoder 1962の解説の解説 - メモとの対応を書いておきます。

A, B, C, ...: $f_i$ に対応
a, b, c, ...: $F_i$ に対応
a + b + c + ...: $G = \sum_{i} F_i$ に対応
全体 ( $(a + b + c + \cdots) / (1 - a - b - c - \cdots)$ ): $G/(1-G)$ に対応

まとめ

結局

A, B, C, ... として繰り返しであるものを考えるとうまいこと等式が成り立つ
「繰り返しであるもの」という制約は実は不要

の 2 点に集約される記事でした。個人的にこの考え方だとしっくりきたので、他の人の役に立つと嬉しいです。

追記 1 (2024-04-16)

類題の解説yukicoder contest 420 H 別解 - つちのこの日記を見て思ったのですが、人々は包除原理を行うときにいちいち「包除原理で加減算したあとの値」に意味を求めたりしないので、ここでも同じように無理に a, b, c, ... に意味を求めなくてよさそうですね。
更に言うとこのテクニック自体が包除原理的かもしれません。

追記 2 (2024-04-16)

A, B, C, ... から a, b, c, ... を作る操作 (元記事の「"それ"を1個以上並べることでオブジェクトを生成する何か」を作る操作) に名前が付いていた方が便利な気がしてきました。
正規表現でいうところの + の逆演算をしているので、invplus と呼びたいです。「繰り返しの逆操作」とかだと長すぎるので…。
それに加え、f という関数で実現されている「同じものが隣にならない繰り返し」のことを nodup と呼びたいです。これは Rust の標準関数 dedup からの類推です。