コンテスト中AC:A〜E
NOMURA Programming Contest 2022（AtCoder Beginner Contest 253） - AtCoder

B - Distance Between Tokens

マンハッタン距離に関する問題です。
'o'である2箇所を $S_{i,j},S_{i',j'}$ とすれば、答えは、

$|i-i'|+|j-j'|$

です。
Submission #32006932 - NOMURA Programming Contest 2022（AtCoder Beginner Contest 253）

C - Max - Min Query

多重集合 $S$ をC++の多重集合multisetで解けます。

実装は後ほど記載のリンク参照。

WAを出したのですが、S.erase(i)をS.erase(x)にしてしまってあり、こうするとSの中のxが全て削除されてしまいます。

補足ですが、Sに追加される個数が高々 $Q$ 個なので、削除される回数も全体で高々 $Q$ 回です。

Submission #32020504 - NOMURA Programming Contest 2022（AtCoder Beginner Contest 253）

D - FizzBuzz Sum Hard

基本的な包除原理です。
$1$ から $N$ までの全体の和 $S$ から不要なものを引くことを考えます。

$1\leq i \leq N$ までの $A,B$ の倍数である $i$ の和を $S_A,S_B$ とおきます。
$S - S_A -S_B$ とすると、 $A$ の倍数かつ $B$ の倍数であるものを余分に1回引いてしまっています。

そこで、 $1\leq i \leq N$ までの $A$ の倍数かつ $B$ の倍数である $i$ の和を $S_{AB}$ とおきます。
すると、 $S - S_A -S_B+S_{AB}$ で答えを求められます。

$A$ の倍数かつ $B$ の倍数である $i$ は、 $A$ と $B$ の最小公倍数を $L$ として、 $L$ の倍数となります。よって、 $S - S_A -S_B+S_L$ を求めればよいです。

具体的な計算方法です。
まず、 $S$ は、 $\frac{N(N+1)}{2}$ です。

$S_A,S_B,S_L$ は以下のように求められます。
$1\leq i \leq N$ に含まれる $X$ の倍数の個数を $n$ とします。 $n$ は下式により求まります。
$n=\lfloor \frac{N}{X} \rfloor - \lceil \frac{1}{X} \rceil +1$

求めたいものは

$S_X=X+2X+\cdots+nX$

なので、

$S_X=X(1+2+\cdots +n)=\frac{Xn(n+1)}{2}$

で求められます。
Submission #32025795 - NOMURA Programming Contest 2022（AtCoder Beginner Contest 253）

E - Distance Sequence

$A_i$ としてあり得るのは $1,...,M$ なので、数列の状態数は、 $NM$ 個であり、DPできそうです。

$dp[i][j]:=$ 数列 $A$ の $i$ 番目が $j$ であるような数列の個数

このテーブルを $i=1,...,N$ の順に更新していくことを考えます。

遷移は、問題文の条件を考えると、

$dp[i][j]\leftarrow (dp[i-1][1]+\cdots\ + dp[i-1][j-K]) + (dp[i-1][j+K]+\cdots\ + dp[i-1][M])$

という感じになります(後の説明のために()で括ってあります)。
愚直に1個ずつ足していくと遷移に時間計算量 $O(M)$ かかり、全体で $O(NM^2)$ となり、間に合いません。

そこで、遷移にかかる計算量を落とせないか考えてみます。
すると、
$dp[i-1][1]+\cdots\ + dp[i-1][j-K]$
及び
$dp[i-1][j+K]+\cdots\ + dp[i-1][M]$
は連続した区間の和となっています。　このような場合、累積和によって、計算量を落とせます。