厳密に記述された解法はもう片方の公式解説をご覧ください。

同じ色同士の区別をなくし、位置 1 には赤がいるとして、最後に \(2(N!)^2\) を掛けることにします。

位置 \(2N-1\) と \(1\) の間に旗を立てます。 走った距離は、旗を横切った回数と言い換えることができます。

旗を横切った回数を、赤が横切った回数と白が横切った回数に分けてそれぞれ考えます。

赤が横切った回数

赤に -1、白に +1 を割り当てて累積話を取ります。すると、累積和の最大値が赤が横切った回数であることが知られています。 実際には、赤から白にロープを貼るイメージで考えると、累積和の -1 倍がその区間に貼られているロープの本数になります。 足りない分は 位置 1 より前より貼られているロープの本数 = 赤が旗を横切った回数になります。

最大値を固定した時の並べ方の数は、カタラン数の拡張によって \(O(1)\) で求まります。

白が横切る回数

位置 1 の特殊性のため、赤の場合の議論をそのまま用いることはできません。

特殊性を弾くために、位置 1 に関わる人を取り除きます。 位置 1 の赤と、最後に走る白の人を除いた上で赤に +1、白に -1 を割り当てて累積和を取ります。 このとき、累積和の最大値 +1 (最後の人に対応) が白の横切る回数であることが同様に示されます。

累積和のグラフを書いてみます。

中身をブラックボックス化し、左端と右端のみに注目した場合、以上の画像のような簡略化ができます。 すると、山の高さのみが問題になるので、最後に走る白が以下のように記述できることがわかる。

• 累積和最小の位置でグラフを区切ったとき(左端と右端はつながっているものとする)、累積和最大を含む区間のうち最右端の区間であって、累積和最小を誘導する -1 の位置

また、左側に累積和最大の部分がないことから、取り除く白は、累積和最小を誘導する -1 のうち最右端のものとしても、横切る回数は同様に求まることがわかる。 この 最右端の白を、美しい白と定義する。

位置 1 と美しい白を取り除いた後の列と、元の列の対応を考える。 ほとんどのケースでは、累積和最小と右端の 2 箇所に白を挿入することで元の列を復元できことから、 取り除いた後の列 1 つに対して、元の列はおおよそ 2 つ対応することがわかる。 特殊なケースでは 1 つしか対応しない。これは、累積和の最小値が 0 である場合である。 このようなケースを取り除きたい。これは Dyck-path の鏡像法と包除原理を適用することで、\(O(N \log N)\) で解くことができます。

よって、全体で \(O(N \log N)\) で解くことができます。

Bonus: \(O(N \log \log N)\) で解くこともできます。