以降では、赤い帽子を被っている人を赤、白い帽子を被っている人を白と呼ぶことにします。

赤同士の並び順、白同士の並び順は、いずれも合計の周回数には影響しません。そこで、赤同士、白同士の区別をなくし、最初の走者が赤であるような並び全てに対する周回数の総和を求め、最後に \(2\times (N!)^2\) をかけるという方針で考えます。

以降では、最後に \(2\times (N!)^2\) をかける前の答えの計算方法について解説します。

---

[1] 並び順が決まっているときの周回数

まず、並び順が決まっているときの合計の周回数 \(T\) について考察していきます。

• \(i=0,..,2N-1\) について、\(a_i\) を \(i\) 番目の人が赤なら \(+1\)、白なら \(-1\) とします (人の番号を 0 から \(2N-1\) で考える)。

• \(i=0,...,2N\) について、\(s_i = a_0+\dots+a_{i-1}\) とし、\(M,m\) をそれぞれ \(s_0,\dots,s_{2N}\) の最大値、最小値とします。

• \(s_i = m\) となる \(i\) を昇順に \(i_1, \dots ,i_k\) とします。

• \(i_0 = 0,~i_{k+1} = 2N\) を用いて、各 \(\ell = 0,\dots,k\) について、番号が \(i_\ell\) 以上 \(i\_{\ell+1}\) 未満である人の集合を \(I_\ell\) とします (\(I_0, I_k\) は空である場合もある)。

このとき、全ての \(\ell = 0,\dots,k-1\) について、\(I_\ell\) に含まれる赤の次に走る白は必ず \(I_{\ell}\) に含まれることがわかります。また、\(I_k\) に含まれる赤の次に走る白は \(I_k\) か \(I_0\) のいずれかに含まれます。

• ちょうど \(t\) 周が終わったときの \(I_\ell\) の中でまだ走り始めていない人の集合を \(I_\ell^{(t)}\) とします。初期状態は、\(I_\ell^{(0)} = I_\ell\) です。

• 集合 \(X = \lbrace x_1,\dots,x_p\rbrace\) (\(x\) 昇順) について、\(F(X),f(X)\) をそれぞれ \(a_{x_1},\dots,a_{x_p}\) の (先頭に \(0\) を加えた) 累積和の最大値、最小値として定義します。

全ての \(\ell =1,\dots,k\) について、\(f(I_\ell^{(0)}) = f(I_\ell^{(1)}) = \dots = 0\) と \(F(I_\ell^{(t+1)}) = \max \lbrace0, F(I_\ell^{(t)})-1\rbrace\) が成り立ちます。

\(F(I_0^{(t)}), f(I_0^{(t)})\) については以下が成立します。ただし、\(0\) 周目が終わったときに走っているのは白とみなすことにします。

• \(t\) 周目が終わったときに走っているのが赤なら、\(F(I_0^{(t+1)}) = F(I_0^{(t)}),~f(I_0^{(t+1)}) = \min \lbrace0, f(I_0^{(t)})+1\rbrace\)

• \(t\) 周目が終わったときに走っているのが白なら、\(F(I_0^{(t+1)}) = \max \lbrace0, F(I_0^{(t)}) -1\rbrace,~f(I_0^{(t+1)}) = f(I_0^{(t)})\)

全ての \(\ell = 0,\dots,k\) について \(F(I_\ell^{(t)}) = f(I_\ell^{(t)}) = 0\) となる最小の \(t\) が、周回数 \(T\) に相当することに注意します。ここで、\(d(\ell,t)\coloneqq F(I_\ell^{(t)}) - f(I_\ell^{(t)})\) とすると、全ての \(\ell, t\) について \(d(\ell,t+1)\geq \max\lbrace0, d(\ell, t) - 1\rbrace\) が従います。また、\(\ell \neq 0\) ならば先述の不等式は常に等号が成立します。ゆえに、\(T\geq \max\lbrace d(\ell, 0)\mid \ell\in\lbrace0,\dots,k\rbrace\rbrace = M-m\) が得られます。

\(d(\ell, M-m) > 0\) となる可能性がある \(\ell\) は \(0\) のみです。 \(t\) 周目が終わったときに走っているのが赤であるような \(t\in\lbrace1,\dots,M-m\rbrace\) の個数は \(-m\)、白であるような \(t\) の個数は \(M\) であることをふまえると、 \(t\) 周目が終わったときに走っているのが赤であるような \(t\in\lbrace0,\dots,M-m-1\rbrace\) の個数、白であるような \(t\) の個数は以下のようになります。

• \(M-m\) 周目が終わったときに走っているのが赤なら、赤 \(:-m-1\)、白 \(:M+1\)

• \(M-m\) 周目が終わったときに走っているのが白なら、赤 \(:-m\)、白 \(:M\)

\(F(I_0^{(0)})\leq M,~f(I_0^{(0)}) = -m\) なので、前者の場合は \(F(I_0^{(M-m)}) = 0,~f(I_0^{(M-m)}) = -1\)、後者の場合は \(F(I_0^{(M-m)}) = 0,~f(I_0^{(M-m)}) = 0\) となります。以上をまとめると、次のことがわかります。

• \(M-m\) 周目が終わったときに走っているのが赤なら、\(T = M-m+1\)
• \(M-m\) 周目が終わったときに走っているのが白なら、\(T = M-m\)

\(M-m\) 周目が終わったときに走っているのが赤であるための必要十分条件を考えます。周の最後に走っているのが赤である場合、その赤は \(I_k\) に含まれます。よって、\(F(I_k^{(0)}) = M-m\) が必要です。さらに、これは十分条件にもなっています。実際、\(F(I_k^{(0)}) = M-m\) のとき、\(m < 0\) かつ \(s_{i_k+1},\dots,s_{2N}\) に \(m\) が現れないことから十分性が示されます。従って、以下のように結論付けることができます。

• \(\max \lbrace s_{i_k},\dots ,s_{2N}\rbrace = M\) なら、\(T = M-m+1\)
• \(\max \lbrace s_{i_k},\dots ,s_{2N}\rbrace < M\) なら、\(T = M-m\)

\(T\) をさらに言い換えることもできます。 \(a\) から \(a_0,~a_{i_k-1}\) を除いた数列を \(b\) とし、その累積和の最大値を \(M'\) とすれば、\(T = M'-m+1\) となります。

---

[2] 数え上げ

\(a_0 = 1\) なる \(+1,-1\) が \(N\) 個ずつ含まれる全ての数列 \((a_0,\dots,a_{2N-1})\) について、前述の \(M'-m+1\) の総和を求めることができれば、全ての並び方に対する周回数の総和を計算できます。

以降では、\(M'\) の総和、\(-m\) の総和、\(1\) の総和を個別に求めていきます。

1 の総和

\(a\) としてありうるものの個数に等しいので、\(1\) の総和は以下のようになります。

\[ \binom{2N-1}{N-1} \]

\(-m\) の総和

\(-m \geq h\) となる \(a\) の個数は、\((1,0)\) から \((N,N)\) への Dyck Path で \(y = x + h\) と交わるものの数に等しく、鏡像法よりこれは \(\binom{2N-1}{N+h}\) であることがわかります。よって、\(-m\) の総和は以下のようになります。

\[\sum_{h=1}^{N-1}\binom{2N-1}{N+h}\]

\(M'\) の総和

\(b\) を固定した際に、元の \(a\) としてありうるものが何個あるかを考えます。そのために、\(b\) の累積和の最小値を \(m'\) として \(m'\) が \(0\) かどうかで場合分けをします。

• \(m' < 0\) の場合
  \(b\) の累積和が \(m'\) となる最も右の位置の右、累積和が \(m'+1\) となる最も右の位置の右が、\(a\) から取り除かれた \(a_{i_k-1} = -1\) の位置の候補です。よって \(a\) としてありうるものは \(2\) 通り。

• \(m' = 0\) の場合
  \(a\) から取り除かれた \(-1\) の位置は末尾しかありえないので、\(a\) としてありうるものは \(1\) 通り。

\(b\) としては \(+1,-1\) が \(N-1\) 個ずつ含まれる全ての数列があり得ますが、その全てに対して \(2M'\) の総和を求めた後、\(m' = 0\) となる \(b\) に対する \(M'\) の総和を引けばよいです。

まず、全ての \(b\) に対する \(2M'\) の総和は、鏡像法を用いることで以下のように書けます。

\[2\sum_{h=1}^{N-1} \binom{2N-2}{N-1+h}\]

次に \(m' = 0\) となる \(b\) に対する \(M'\) の総和を考えます。 \(m' = 0,~M'\geq h\) となる \(b\) の個数は

\[\sum_{k=1}^{\infty} \left\lbrace\binom{2N-2}{N-k(h+1)} - 2 \binom{2N-2}{N-1-k(h+1)} + \binom{2N-2}{N-2-k(h+1)} \right\rbrace\]

であることが知られています (証明は割愛しますが、”catalan tree average height” などで検索すると、文献が出てきます)。上式は無限和の形になっていますが、実際には \(k(h+1)\leq N\) となる \(k\) の範囲だけ足せば十分です。以上より、全ての \(a\) に対する \(M'\) の和は以下のようになります。

\[2\sum_{h=1}^{N-1} \binom{2N-2}{N-1+h} - \sum_{h=1}^{N-1}\sum_{k=1}^{\infty} \left\lbrace\binom{2N-2}{N-k(h+1)} - 2 \binom{2N-2}{N-1-k(h+1)} + \binom{2N-2}{N-2-k(h+1)} \right\rbrace\]

これは \(O(N\log N)\) 時間で計算できます。