問題は以下のように言い換えられます。

各要素が \(1,-1\) のいずれかであるような \(N\) 個の整数列の組 \(X_1,X_2,\dots,X_N\) であって、以下の条件をすべて満たすものが存在するか判定してください。

• 各整数列の長さはちょうど \(2K\)
• 整数列 \(X_i\) の \(j\) 項目の値を \(X_{i,j}\) としたとき、 \(\sum_{j=1}^{k} X_{i,j}\) は非負整数である
• \(\sum_{j=1}^{2K} X_{i,j}=0\) が成り立つ
• 各 \(j=1,2,3,\dots,2K\) に対し、 \(X_{i,j}\) が \(1\) であるような \(i\) の個数はちょうど \(A_j\) 個

各数列が空である状態からはじめて、\(k=1,2,\dots,2K\) 項目の順に \(A_k\) 個の \(1\) と \(N-A_k\) 個の \(-1\) を割り振ることを考えます。

割り振りの際、 \(1\) をできるだけ \(k-1\) 項目までの和が低い数列に割り振るようにしてみると、 \(\sum_{j=1}^{k} X_{i,j}\) の最大値と最小値の差が \(2\) 以下に抑えられることが帰納法により示せます。するとこの割り当て方によって、 \(\sum_{j=1}^{k} X_{i,j}\) が非負整数であるような \(i\) の個数は最大化されています。よって、この割り当てによって \(\sum_{j=1}^{k} X_{i,j}\) が負になるような \(i\) が生じた場合、答えは No です。

逆にこの割り当てで \(1,2,4\) 番目の条件が満たされるとき、 \(3\) 番目の条件が満たされるのはどのようなときか考えます。まず \(\sum_{i=1}^{N}\sum_{j=1}^{2K} X_{i,j} = \sum_{j=1}^{2K} (2A_j-N)\) が \(0\) であることが必要です。逆にこれが満たされている場合、 \(\sum_{j=1}^{2K} X_{i,j}\) の最大値と最小値の差が \(2\) 以下に抑えられることから、 \(3\) 番目の条件が満たされていることが分かります。

以上の計算により \(O(K)\) 時間で判定ができます。