数列が Polish であることの言い換え

非負整数列 \((V_1,\dots,V_N)\) に対応する次のようなグリッド上の経路を考えます。

• \((0,1)\) から始めて、\(i=1,\dots,N\) についてこの順に、\(y\) 軸正方向に \(V_i\) だけ進んだあと \(x\) 軸正方向に \(1\) 進む。

この経路が \((0,0),\dots,(N-1,N-1)\) を通らずに最終的に \((N,N)\) にたどり着くことと、 \((V_1,\dots,V_N)\) が Polish であることは同値です。このことは、数学的帰納法で定義に従って証明できます。

辞書順制約のための場合分け

以上の言い換えから、\((A_1,\dots,A_N)\) が Polish であるかは \(O(N)\) で判定できます。

次に、辞書順で \((A_1,\dots,A_N)\) 未満の数列を処理するために、場合分けをします。具体的には、\(i=1,\dots,N\) と \(a<A_i\) について、\((A_1,\dots,A_{i-1}, a)\) で始まる数列に分けて考えていきます。ただし、このままだと \(A_1+\dots+A_N\) で \(O(N^2)\) 通りの場合分けになってしまうため、工夫が必要です。

\((A_1,\dots,A_{i-1}, a)\) で始まる数列に対応するグリッド上の経路を観察すると、これは途中まで \((V_1,\dots,V_N)\) に対応する経路と一致していますが、途中から横（\(X\) 軸正方向）に逸れることが分かります。また、\(i\) や \(a\) の選び方による場合分けは、どの点から横に逸れるかで場合分けをしていることが分かります。グリッド上の経路の \(y\) 座標が \(N\) を超えてしまうと \((N,N)\) にはたどり着けないことから、実際に試すべき候補は \(N\)  通り程度しかありません。

数え上げ

あとは各場合について数え上げるだけです。整理すると、\(O(N)\) 個の座標 \((x,y)\) について、\((x,y)\) から \((N,N)\) へのグリッド上の経路のうち \((0,0),\dots,(N-1,N-1)\) を通らないものを求められればこの問題が解けます。

この問題は、最短経路を使ったカタラン数の一般項の求め方（参考）と同様の方法で求めることができます。具体的には、\((x,y)\) から \((N-1,N)\) への経路の数から \((y,x)\) から \((N-1,N)\) への経路の数を引けばよいです。

C++による実装例