穴あきグリッドにおける有効な正方形の数え上げと動的計画法による最適化
$H \times W$ のグリッド上に $N$ 個の「穴（障害物）」が存在する際、穴を一切含まない正方形がいくつ存在するかを計算する問題は、動的計画法（DP）の典型的な応用例です。本記事では、この問題に対する直感的だが誤ったアプローチの分析と、それを修正した最適なアルゴリズムについて解説します。
誤ったアプローチ：独立した連続長に基づく累積和
まず考えられがちな ...
10月14日 09:16 投稿
競プロ典型問題の解法パターンと実装テクニック
文字列の構成要素検証
与えられた3文字の文字列が"A"、"B"、"C"の3種類の文字のみで構成されているかを判定する問題。文字の順序は問わず、各文字が1回ずつ出現するかを確認する必要がある。
#include <iostream>
#include <array>
using namespace std;
int main() {
string input;
cin >> input;
array<int, 3> count = {0};
...
8月27日 22:31 投稿