問題文https://codeforces.com/problemset/problem/1268/B 列からなる高さがそれぞれ のヒストグラムがある。 であり、広義単調減少になっている。 このようなヒストグラムから、 であるか であるような長方形を何個作ることが出来るかという問題。制約 解法…

問題atcoder.jp 高橋くんが、まだ辺が存在しない $N$ 頂点のグラフに、 \(M\) 回任意の頂点へ移動しながら有向辺を張っていく。はじめは頂点 $1$ にいる。 \(M\) 回の移動後にそのグラフが強連結になっているような移動の仕方の通りの数を求める問題。制約$1…

atcoder.jp$0$ か $1$ を末尾に挿入,末尾削除をする操作を $N$ 回行って、最終的に文字列 $S$ にする操作列の場合の数を求める問題。 $1 \leq N \leq 5000$ と大きい。解法実は、同じ長さの文字列であれば操作列の場合の数は全て同じになる。なぜなら、操作…