ヒント集 → https://atcoder.jp/contests/arc197/editorial/12811

[1] \((x,y)\) を黒く塗ることが可能かの判定

まずは数え上げ対象となるマスがどのようなものであるかの条件を整理しましょう．

マス \((x,y)\) を黒く塗ることができるという条件は，

• \(X\) の左 \(x+y-2\) 文字分を上手く決めることで，\((1,1)\) から \((x,y)\) に到達できる．
• \(X\) の右 \((H+W-x-y)\) 文字分を上手く決めることで，\((x,y)\) から \((H,W)\) に到達できる．

と分解できます．

前者の条件をさらに整理しましょう．\(S\) の左 \(x+y-2\) 文字分について，そこに含まれる D の個数を \(D\)，R の個数を \(R\) とすれば，条件は \(D\leq x-1\) かつ \(R\leq y-1\) と言い換えられます．

後者の条件も同様に，\(H-x\), \(W-y\) がいくつ以上という形で言い換えることができます．

\(O(H+W)\) 時間かけて適当な累積和を前計算しておくことで，固定された \((x,y)\) に対してこの判定問題は \(O(1)\) 時間で解けるようにます．

[2] 数え上げ

判定方法は理解できましたが，答を高速に求めるにはさらにいくつかの条件を満たすマスをまとめて数え上げる必要があります． この際，何らかの値によって分類して数えるというのが定石です．

\(x\) の値や \(y\) の値によって分類するという方針で解くこともできますが，本問では \(x+y\) の値によって分類するのが最も簡潔です．

つまり \(k=2,3,\ldots,H+W\) に対して，\(x+y=k\) であるようなマスの数え上げを行うことを考えます．[1] で述べたことを踏まえると，数えるべき \((x,y)\) は適当な定数 \(a,b,c,d\) について \(a\leq x\leq b\) かつ \(c\leq y\leq d\) を満たすものだと言い換えられます．さらに \(y=k-x\) を用いて後者の条件を書き換えると，条件はすべて \(x\) の範囲として書けるため，数え上げは簡単に行えます．

以上を適切に実装すれば，\(O(H+W)\) 時間で答を求めることができます．

• 解答例：https://atcoder.jp/contests/arc197/submissions/65380292