Hints: https://atcoder.jp/contests/arc197/editorial/12878

[1] Determining whether \((x,y)\) can be painted black

First, let us clarify the conditions that characterize the cells we need to count.

The condition for being able to paint cell \((x,y)\) black can be decomposed into two requirements:

• By appropriately choosing the first \(x+y-2\) characters of \(X\), you can move from \((1,1)\) to \((x,y)\).
• By appropriately choosing the last \(H+W-x-y\) characters of \(X\), you can move from \((x,y)\) to \((H,W)\).

Let us analyze the first requirement. Let \(D\) and \(R\) be, respectively, the number of D’s and R’s among the first \(x+y-2\) characters of \(S\). Then, the condition is \(D\leq x-1\) and \(R\leq y-1\).

Similarly, the second requirement can be rephrased in terms of bounds on \(H-x\) and \(W-y\).

By precomputing suitable prefix sums in \(O(H+W)\) time, each fixed \((x,y)\) can be tested in \(O(1)\) time.

[2] Counting

Having understood how to test a single cell in \(O(1)\), we must still count all qualifying cells efficiently. A standard approach is to classify cells by some parameter.

In this problem, the simplest choice is to classify by the sum \(x+y\).

Concretely, for each \(k=2,3,\ldots,H+W\), consider all cells satisfying \(x+y=k\). From the analysis in [1], the permissible \((x,y)\) can be described by inequalities of the form \(a\leq x\leq b\) and \(c\leq y\leq d\) for some constants \(a, b, c, d\). Substituting \(y = k - x\) converts the second inequality into another bound on \(x\), so the valid \(x\)’s form a single interval.

By implementing this properly, the answer can be found in \(O(H+W)\) time.

• Sample implementation: https://atcoder.jp/contests/arc197/submissions/65380292