Permutation Oddness が解けるまで -

橙埋め最後の砦となっていた問題が解けたので，解けるまでの思考を書いてみます．解けたと言っても，準犯罪 AC のような感じですが，想定解法 *1 と全然違う多項式時間アルゴリズムを作って面白かったというのもあります．ひたすら別解の話を書くだけなので，綺麗な想定解法を知りたい方はこちらへどうぞ．

問題概要

$\{1, 2, \dots, n\}$ の順列 $p = (p_1, p_2, \dots, p_n)$ の奇妙さを $\sum_{i = 1}^n |i - p_i|$ で定義する．奇妙さが $k$ であるような $\{1, 2, \dots, n\}$ の順列の個数を求めよ．*2

序盤（ 9 月末）

問題を見て，シンプルな問題だな～と思う．しかし全然手が付けられず，とりあえず $n \leq 10$ で全列挙して， $(n, k)$ に関して表にして結果を眺める．何も分からん．

制約が $n \leq 50$ なので，列挙を高速化する程度では全然間に合わない．一箇所固定して小さい問題（いくつか）に帰着して再帰？みたいなことを考え，先頭が $j \in \{1, 2, \dots, n\}$ であるような場合の数を表にして結果を眺める．何も分からん，アゲイン．

あ！こういうのは前から順に固定して DP をやるんですよね～． $\{p_1, p_2, \dots, p_j\} = X$ であり， $\sum_{i=1}^j |i - p_i| = y$ であるような場合の数を $\mathrm{dp}(X, y)$ として前から計算すれば OK．

間に合うはずがない．たぶん $\mathrm{O}(2^n n^3)$ だから，定数倍速くして $n \leq 20$ ぐらいならなんとかなるかな？という感じ．もー無理，はい積みます！

中盤（～ 12 月中旬）

月に 2, 3 回見に行って考えるけど何も進まない．橙を今年中に埋めるという目標が絶望的に感じられる．

今年中に橙埋めたい（願望）
— ⚫️Y.Y.⚪️ (@ygussany) 2020年10月19日

終盤 1 （ 12/24 ～ 12/25 朝）

クリスマスということで，サンタさんがプレゼントとして天啓を授けてくれました．

🎅「順列を括弧列として見るのはどうじゃ？」

各 $i$ から， $p_j = i$ であるような $j$ に向かって有向辺を張ると，順列 $p$ は $\{1, 2, \dots, n\}$ を有向閉路に分解します．たとえば， $p = (4, 3, 1, 2, 7, 5, 6)$ であれば， $(1, 3, 2, 4)$ と $(5, 6, 7)$ に分解されます．

この分解を見て，自身より大きい点 $2$ つと隣接する点に開き括弧，小さい点 $2$ つと隣接する点に閉じ括弧，それ以外の点にドット $\bullet$ を置くことにすると，任意の順列を正当な括弧列（＋ドット）に対応付けることができます．たとえば，上の例だと $( ( ) ) ( \bullet )$ となります．

このように順列を括弧列に写す写像は単射ではありません．たとえば， $p' = (4, 3, 2, 1, 7, 6, 5)$ は $(1, 4), (2, 3), (5, 7), (6)$ の $4$ つの有向閉路に分解され，同じ $( ( ) ) ( \bullet )$ に対応付けられます．しかし，対応する括弧列が同じ順列は，すべて同じ奇妙さを持ち，それは以下のように計算できます．

まず，有向辺 $(i, j)$ の長さを $|i - j|$ と定義すると，順列の奇妙さは，上の方法で得られる有向閉路の長さの総和 $S$ に等しいです．この総和 $S$ を別の方法で数えてみましょう．

各区間 $(i, i+1)$ を有向辺が（どちら向きでも）跨ぐ合計回数を $c_i$ とします．すると，明らかに $S = \sum_{i=1}^{n-1} c_i$ が成り立ちます．この $c_i$ を括弧列の方で評価する方法を考えてみると，実はこれは区間 $(i, i+1)$ が「何重に括弧の中に入っているか」のちょうど $2$ 倍に等しいことが分かります．何故なら，区間 $(i, i+1)$ が $d_i$ 重に括弧の中に入っていれば，その区間より左に「自分より大きい点 $2$ つに隣接する点」が「自分より小さい点 $2$ つに隣接する点」よりちょうど $d_i$ 個多く存在し，その余剰分の $2$ 倍だけ区間を跨ぐ辺が伸びているはずだからです．すなわち， $S = 2\sum_{i=1}^{n-1} d_i$ が成り立ちます．

というわけで，括弧列（ドットを含む）を $1$ つ固定すると，それに対応する順列の奇妙さはすべて同じであり，簡単に（ $\mathrm{O}(n)$ 時間で）計算できることが分かりました．あとは，括弧列を全列挙して，各括弧列に対応する順列の個数が計算できれば，奇妙さが $k$ であるような順列の個数が計算できることになります．そして，これは次のようにまたしても簡単に（ $\mathrm{O}(n)$ 時間で）計算できることが分かります．

先ほどは各区間が何重に括弧の中に入っているかに注目しましたが，今度は各点（括弧，ドット）が何重に括弧の中に入っているかに注目しましょう．まず，ドットを無視して，閉じ括弧があるような点 $i$ に伸びてくる有向辺 $(j, i)$ の始点 $j \lt i$ を，括弧の内側から順に決めていきます． $i$ が $e_i$ 重に括弧の中に入っていれば，自身の内側にある閉じ括弧に関してすべて決めた後，そのような $j$ の選び方は $e_i + 1$ 通り *3 あります．同様に，開き括弧があるような点 $i$ に伸びてくる有向辺 $(j, i)$ の始点 $j \gt i$ も $e_i + 1$ 通りあります．最後に，ドット $\bullet$ があるような点 $i$ が $e_i$ 重に括弧の中に入っていれば，次のいずれか一方が必ず成り立ちます．

$i$ を跨ぐ有向辺がちょうど $2e_i$ 本あって，自身は不動点 $p_i = i$ となっている．
$i$ を跨ぐ有向辺がちょうど $2e_i - 1$ 本あって，自身はより小さい点とより大きい点に隣接する．（上で決めた有向辺のいずれかの中継点となる．）

したがって，このような点の状態は（他の点の状態に依らず） $2e_i + 1$ 通りです．

以上をまとめると，括弧列を固定したとき，それに対応する順列の総数は

\begin{align}
\prod_i \{\, e_i + 1 \mid 点~i~には括弧がある \,\} \prod_i \{\, 2e_i + 1 \mid 点~i~にはドット\bulletがある \,\} \tag{1}
\end{align}

であることが分かりました．これにて一件落着，めでたしめでたし．

とはいかないんですよね．括弧列を列挙すると言いましたが，いくつあると思っているんですか？ドットを無視してもカタラン数 $\frac{1}{n'+1}\binom{2n'}{n'}~~\left(n' = \left\lfloor\frac{n}{2}\right\rfloor\right)$ だけあるので，やっぱり指数的に大きいんですよね．とはいえ， $n \leq 30$ ぐらいまでならなんとかなりそうになって，だいぶ進捗した気分にはなりました．

終盤 2 （ 12/25 夜）

括弧列を全列挙するのは絶望的ですが，上の議論をよく見直してみると，「何重に括弧に入っている点・区間がそれぞれ合計いくつあるか」だけが重要であることが分かります．したがって，たとえば $( ) ( \bullet ( ) )$ と $( ( ) ) ( \bullet )$ は同じ特徴の括弧列として扱えるはずです．というわけで，各深さに括弧とドットをいくつずつ配置するかを固定して，それで生成される括弧列が何通りあるかを考えてみましょう．

深さ $i = 0, 1, \dots, n'$ に括弧を $a_i$ 組，ドットを $b_i$ 個配置するとします．たとえば，上の例だと

\begin{align}
a_0 = 2,~a_1 = 1,~a_i = 0~~(i \geq 2)\\
b_0 = 0,~b_1 = 1,~b_i = 0~~(i \geq 2)
\end{align}

となります．明らかに， $n = \sum_i (2a_i + b_i)$ が成り立ちます．また，深さ $i + 1$ に何かを配置するためには， $a_j \geq 1~~(0 \leq j \leq i)$ でないといけません．逆に，これらの条件を満たすような括弧列は必ず構成できます．（以下で構成します．）

深さ $i$ 未満までの括弧列を構成したとして，深さ $i$ の部分の配置を何通り選べるかを考えてみましょう．まず，深さ $i$ に配置すべき $a_i$ 組の括弧 $()$ と $b_i$ 個のドット $\bullet$ を一列に並べます．これは $\binom{a_i + b_i}{a_i}$ 通りあります．次に，その間に $(a_{i-1} - 1)$ 個の仕切りを入れて区切ることで，深さ $i - 1$ に配置されている $a_{i-1}$ 個の括弧のどれに先ほど並べたもののどこからどこまでを入れるかを選びます（ここで，仮想的に $a_{-1} = 1$ とします）．そのような選び方は $\binom{a_i + b_i + a_{i-1} - 1}{a_{i-1} - 1}$ 通りあり，したがって合計で

\begin{align}
\prod_{i=0}^{n'} \binom{a_i + b_i}{a_i}\binom{a_i + b_i + a_{i-1} - 1}{a_{i-1} - 1} = \prod_{i=0}^{n'} \frac{(a_i + b_i + a_{i-1} - 1)!}{a_i!b_i!(a_{i-1} - 1)!} \tag{2}
\end{align}

通りの括弧列が構成できることが分かりました．

これで， $(1)$ と $(2)$ を掛ければ，条件を満たす数列 $a_i, b_i$ から構成できる順列の個数が分かり，また各数列から構成される奇妙さも計算できます．しかし，これでもまだ数列の数が多過ぎて *4 全探索は無理（ $n \leq 40$ ぐらいまでは大丈夫）でした．

最後の仕上げは，やはり DP です．条件でもあるように，浅い方に括弧が $1$ つ以上無いと深さは進められないので，「深さ $\ell$ までで $m$ 個の点に括弧・ドットを配置し，深さ $\ell$ には $q$ 組の括弧を配置し，そこまでで得られる奇妙さの合計が $z$ であるような組合せの総数」を $\mathrm{dp}(\ell, m, q, z)$ として，これを浅い方から順に計算することにしました．幸いなことに， $(1)$ も $(2)$ も奇妙さも，これだけの情報があれば途中経過を正しく計算できます．

表のサイズが $2\cdot(n')^5 \leq 2 \cdot 10^7$ 程度で，遷移に $\mathrm{O}(n^2)$ 時間かけているので，これでも絶望的 *5 に見えますが，実際に計算すべき場所はそれほど多くないことに気付き，適当にサボって高速化することでなんとか通すことができました！