Zig-Zag Numbers

条件を満たすような○○以上△△以下の整数を求める問題は、上の桁から決めていくDPがよく使われる。DEGwer さんの記事いわく、下から決める方法も上手くいくらしいので、Zig-Zag Numbers と呼ばれる非常に面倒な問題を下からの桁DPで解いてみた。

F - ジグザグ数 (Zig-Zag Numbers)

下から決めていく桁 DP なのだけど、Ordering モノイドを使うと見通しが良いかもしれない。最近の言語とかだと標準で使われている概念なので知っている人も多いと思うが、一応説明しよう。Ordering モノイドというのはモノイドで、$\mathtt{EQ},\mathtt{LT},\mathtt{GT}$ の 3 種類の値を取る。二項演算は以下で定義される。

EQ * x = x
LT * x = LT
GT * x = GT

Haskell だと compare が Ordering を返す。

Prelude> compare 1 2
LT
Prelude> compare 2 2
EQ
Prelude> compare 3 2
GT
Prelude> :t compare
compare :: Ord a => a -> a -> Ordering
Prelude>

これは何者なのかというと、長さの等しい 2 つのリストを辞書順比較するときに自然に現れるものである。 比較する2つのリストを$x=[3,1,4,2,5,9,1], y=[3,1,4,1,5,9,2]$とする。各要素を比較すると $[\mathtt{EQ}, \mathtt{EQ}, \mathtt{EQ}, \mathtt{GT}, \mathtt{EQ}, \mathtt{EQ}, \mathtt{LT}]$となる。これを$\mathtt{fold}$で畳み込むと何が起きるかというと、foldr なら、

\begin{align}
& \mathtt{foldr}([{\mathtt{EQ}, \mathtt{EQ}, \mathtt{EQ}, \mathtt{GT}, \mathtt{EQ}, \mathtt{EQ}, \mathtt{LT}}]) \\
=& \mathtt{EQ} \ast \mathtt{foldr}([{\mathtt{EQ}, \mathtt{EQ}, \mathtt{GT}, \mathtt{EQ}, \mathtt{EQ}, \mathtt{LT}}]) \\
=& \mathtt{foldr}([{\mathtt{EQ}, \mathtt{EQ}, \mathtt{GT}, \mathtt{EQ}, \mathtt{EQ}, \mathtt{LT}}]) \\
=& \mathtt{EQ} \ast \mathtt{foldr}([{\mathtt{EQ}, \mathtt{GT}, \mathtt{EQ}, \mathtt{EQ}, \mathtt{LT}}]) \\
=& \mathtt{foldr}([{\mathtt{EQ}, \mathtt{GT}, \mathtt{EQ}, \mathtt{EQ}, \mathtt{LT}}]) \\
=& \mathtt{EQ} \ast \mathtt{foldr}([{\mathtt{GT}, \mathtt{EQ}, \mathtt{EQ}, \mathtt{LT}}]) \\
=& \mathtt{foldr}([{\mathtt{GT}, \mathtt{EQ}, \mathtt{EQ}, \mathtt{LT}}]) \\
=& \mathtt{GT} \ast \mathtt{foldr}([{\mathtt{EQ}, \mathtt{EQ}, \mathtt{LT}}]) \\
=& \mathtt{GT}
\end{align}

辞書順比較そのものであることが確認できる。モノイドになっているので、当然どのような順序で計算しても結果は同じになる。

上からの桁 DP をする場合、Ordering モノイドは一度 $\mathtt{LT}$ か $\mathtt{GT}$ になったら変化しないので、状態は 2 つあれば区別がつく($\mathtt{GT}$は無視できるため)。しかし下から桁 DP をする場合は、Ordering モノイドはいくらでも変化しうるので 3 状態持たなければならない。

https://beta.atcoder.jp/contests/joi2012yo/submissions/1893277