はじめに
競技プログラマ的な視点で「列挙問題」について解説してみる，という記事です．競技プログラミング要素はこれだけです（ごめん）．元々脈絡無く用意していた記事ですが，Competitive Programming (1) Advent Calendar 2020 の枠が変に空いていたので入ってみました．無難に色変記事とかに差し替えるかとも思いましたが，それはそれで巷にたくさんあるので独自性重視でこのまま敢行します．
本稿では，列挙問題と呼ばれる問題と，それに対するアプローチのひとつ，Reverse Search （逆探索）と呼ばれる手法について，一競技プログラマとして理解しやすかった文脈で以て解説していきます．普段のコンテストで使う考え方とは違う部分も多く，わたしとしては興味深かったので，面白さを伝えられれば幸いです．列挙とそれに関連する概念を輸入しておいたらそういう出題が増えたりしないかな，とはちょっと思っています（難しいとも思っていますが）．
列挙問題
列挙問題とは，例えば「ある集合 $X$ の要素 $x \in X$ を，すべて，かつ，重複無く出力せよ」といった形で書かれる問題です．競技プログラミングではそんなにメジャーではない分野な気がしますが，例えば（部分問題としてしばしば出てくる）「約数列挙」などは列挙問題と言えるでしょう．ただし，一般には，列挙する対象の個数が（何らかのパラメータに対して）多項式個だとは限らないため，やや出題しづらい印象はあります．詳しく見てみましょう．
解のサイズと計算量評価
列挙対象とする集合 $X$ として特に特別な仮定をしない場合，そのサイズ $|X|$ が「多項式個」であるとは限りません．例えば，$n$ 頂点の Interval Graph の個数は頂点数 $n$ に対して多項式個ではりません．
競技プログラミングの文脈で（時間）計算量を評価するとき，大抵の場合は，
- アルゴリズムの開始から終了までの全体の時間を
- 計算量の上界で
評価することに興味があります．ですが，出力するべき文字列の長さ*1がそもそも入力サイズの指数倍だとすると，あらゆるアルゴリズムは指数時間ということになってしまってやや議論が雑になってしまいます．そこで，列挙問題の文脈では，もうちょっと違う方法で計算量を評価します．
そこで登場する評価方法がいくつかあるのですが，ここでは割と強い要求である「多項式時間遅延」というものを紹介します．これは，アルゴリズムの開始から終了までの全体をまとめて評価する代わりに，
- 実行開始から $1$ 個目の出力が得られるまでの時間
- （valid な $i$ について）$i$ 番目の出力が得られてから，$i + 1$ 番目の出力が得られるまでの時間
- 最後の出力から，アルゴリズムが終了するまでの時間
にバラして着目して，そのすべてが入力サイズの多項式倍で抑えられていることを言います．雑な図（と英語？）で言えば，次のようにアルゴリズムの全体にかかる時間を評価するのではなく（矢印が時間軸だと思ってください），
次のように各出力が得られるごとに時間軸を区切ってそれぞれが多項式時間ならばよい，ということです．
ナイーブなアルゴリズムとその計算量
具体例をイメージできていた方が分かりやすいと思うのでまず例を挙げます．先程ちょっとだけ言及したグラフ列挙の場合，例えば下図のように，グラフを頂点に対応付けて適当な隣接関係を付けた，いわばメタなグラフを考えることができます．
この例は 4 頂点のグラフ全体を頂点集合として，1 本の辺の足し引きを隣接関係（辺）としたグラフです．このグラフに対して頂点が重複しないように例えば DFS でトラバースをする場合，例えば次のような DFS Tree が構成されます（DFS 中で辺を辿ったとき，その訪問先から訪問元への向きで有向化しています）．
（なにやら図がちょっとズレてますが，気にしないでください……．使い回しなので仕方が無いということでここは一つ．） こういう気持ちになると，列挙というのは，列挙したい対象を頂点とし，頂点間に適当な隣接関係を付けたグラフに対する DFS に見えてきます．
グラフに対するよくある DFS を思い出してみると，次のような，極めて見覚えのある形の擬似コードで表されるアルゴリズム……，というか，よくある DFS そのもので列挙兼トラバースを行うことができます．
dfs( 現在訪問中の頂点 u, 過去に出力したことがある頂点の集合 P )
{
output( u );
for ( v : u の隣接頂点 )
{
if ( v が P に含まれない )
{
dfs( v, P に u を加えた集合 );
}
}
}これでできるにはできるのですが，このアルゴリズムの場合，「$v$ が $P$ に含まれない」をチェックするときに，今までに訪問した頂点の個数についての多項式倍の時間（または空間）がかかってしまいます．こういった，各出力ごとに「過去に出力した個数に関する多項式」時間がかかるアルゴリズムの計算時間を，「Incremental Polynomial 時間」と呼びます．これは，出力の個数が指数のときは指数時間遅延です*2．この Incremental Polynomial を多項式時間遅延に改善するのが，Reverse Seearch （逆探索）[1] です．
Reverse Search （逆探索）
先程図示したような，有向化された DFS Tree における 2 頂点間の有向辺について，指されている方を親，指している方を子と呼ぶことにします．DFS Tree というのは通常，「DFS をやった結果，使われた辺だけを集めてきたグラフ」として定まりますが，根を除いた各頂点に対して親は常に一つであることを利用して，頂点 $v$ の親 $\mathit{ parent }( v )$ を決める関数 $\mathit{ parent }$ を定めることでも同等の木が（implicit に）定まります．この関数があれば，先程の擬似コードを少し変更して，
dfs( 現在訪問中の頂点 u )
{
output( u );
for ( v : u の隣接頂点 )
{
if ( u == parent( v ) )
{
dfs( v );
}
}
}
- 過去に訪問（出力）した頂点の集合をもたなくなった
- $u$ の隣接頂点 $v$ を訪問するかの判定に $u = \mathit{parent}( v )$ という条件を使うようになった
の 2 点です．これに対応する計算量的な改善としてはそれぞれ，
- $u$ の表現が多項式長で，DFS Tree の深さが多項式だという仮定の下，Extra Memory が多項式領域
- $\mathit{parent}( v )$ の計算と頂点の等価判定が多項式時間という仮定の下，多項式時間遅延
になっています．仮定が長くてうるさいですが，これは列挙の対象によるので「そうできるならば」という条件付きのまま置いておきます*4．
このようにして，ローカルな情報だけを使って DFS をして，ナイーブ DFS の遅延の意味での計算量を改善する手法が Reverse Search です．ローカルな情報だけを使うので並列化（というか分散化）しやすいというメリットもあります．
なお名前の由来ですが，親を定義しておいてから子方向に向かって探索を進めるあたりが「逆」です．
おわりに
ということで，列挙問題の導入と Reverse Search の紹介でした．ややスレチ（死後）的な話題でしたが，少しでも面白さが伝われば幸いです．
最後に追加の参考文献ですが，より網羅的な文献として [2] がおすすめです．
参考文献
[1] Avis, D., & Fukuda, K. (1996). Reverse search for enumeration. Discrete applied mathematics, 65(1-3), 21-46.
[2] 岡本吉央. (2012). 列挙の基本と基礎的なアルゴリズム. 電子情報通信学会誌, 95(6), 477-483.
