ABC311 F DP+累積和解法
解説とは少し違う方法な気がしています。本質的に同じになるかもしれませんが、詰めるのが面倒くさい。
各列について考えます。美しいグリッドの各列は下から何マスか黒色で、その上はすべて白色になります。各列何マスを黒色にできるかは、その列が元々どのように黒色に塗られていたかと、左右の列の塗り方によります。したがって、「i列目をkマス黒色に塗るときの、i列目までの塗り方の通り数」をDPすればよいです。以後DP[i][j] とします。
i列目の下からj' マス目が元々黒色のとき、i列目をj (＜j') マス黒色に塗ることはできません。すなわち、DP[i][j]=0 (j=0,1,..., j' - 1)。
i列目をjマス黒色に塗るには、i-1列目がj+1より大きいマス黒色に塗られていてはいけません。逆に言えば、0マス～j+1マス黒色に塗られているのはOKです。したがって、DP[i][j] = DP[i-1][0] + DP[i-1][1] + ... + DP[i-1][j + 1]。
これはもちろん律儀に計算していると間に合わないので、累積和を求めておきます。副作用として、最終的な答えがCum[M-1][N]=DP[M-1][0]+DP[M-1][1]+...+DP[M-1][N]と求まっています。これにより、O(NM) で計算でき、十分に高速です。
右から決めていくほうが制約が強くて良さそうな感じがしますが、強い分部分和を求める必要があり、累積和でウッとなることになります。その点、左から決めていく方法であればつねに0～j+1の和であるので、0に番兵を置いて良い感じにしなくても済むというメリットがあります。
私は（特に本番でない場合）DPの計算に必要でない部分はすぐに捨てるタチなのでこのように捨ててやっていますが、混乱する人はすべてのDPの値と累積和を保存しても間に合います。
ところで、こうやって捨てていると、上の提出でもまだ無駄な部分が見えてきます。まず、DPの値を求めてから累積和を計算していますが、DP[i][j]の値が求まったそばから次のCum[i][j]を計算しても問題ありません。DP[i][j+1]の計算に必要なのはCum[i-1][j+2]またはCum[i-1][j+1]なので、Cum[i][j]を新しい配列Cum[i]に入れておく必要もなく、常にCum[i-1][j]に上書きして問題がありません。これにより、Cumは一つの一次配列Cumのみを使い回すことで計算が済みます。また、DP[i][j]の値は、Cum[j]を計算するのにしか用いませんから、二次配列DPどころか、一次配列DP[i]を保持する必要もありません。Cum[0]=DP[0]のみ別に計算する必要があることに注意してください。
DP[i][j]の値をxと置いたのが以下の提出です。
atcoder.jp
それも省くと以下になります。Cum[j] = Cum[j - 1] + (j >= st) * Cum[min(N, j + 1)]はもはや何を計算しているのかよくわからないですね。
atcoder.jp
