\(N=13\) のとき、経路の個数は \(\binom{24}{12}-1 = 2704155\) 個で、\(6 \times 10^6\) には \(2\) 倍程度の余裕しかありません。

実は、スコアとして \(0 \dots \binom{2N-2}{N-1}-1\) をタイトに作ることが出来ます。

\(1\) 行ずつ追加しながら、各行を右から順に以下のように埋めることが出来ます。

0  0  0  0  0  0
1  1  1  1  1  0
2  3  4  5  5  0
4  7 11 15 15  0
 ... 25 35 35  0

具体的には、\((1,1)\) から \((i,N)\) の経路について「下移動を 0、右移動を 1 とした列を reverse したもの」の辞書順 (0-indexed) とスコアが一致するように書き込めば良いです。\((1,1)\) から \((i,j)\) の経路のスコアの集合が連続した整数の集合になることを利用して実装すると良いでしょう。

ソースコード

想定誤方針

 0  0  0  0  0
 1  2  4  8 16
 0  0  0  0  0
 4  8 16 32 64
 0  0  0  0  0

のように \(i\) 歩目の分岐を \(2^i\) に対応させる構成では、スコアの max が \(2^{23}-1=8388607\) でオーバーします。この方針のままスコアの max を改善する方法は、少なくとも writer は思いついていません。