穴あきグリッドにおける有効な正方形の数え上げと動的計画法による最適化
$H \times W$ のグリッド上に $N$ 個の「穴（障害物）」が存在する際、穴を一切含まない正方形がいくつ存在するかを計算する問題は、動的計画法（DP）の典型的な応用例です。本記事では、この問題に対する直感的だが誤ったアプローチの分析と、それを修正した最適なアルゴリズムについて解説します。
誤ったアプローチ：独立した連続長に基づく累積和
まず考えられがちな ...
10月14日 09:16 投稿
二次元グリッドの最小経路を求める動的計画法の実装
問題の概要
左上のセル (0, 0) から右下のセル (m-1, n-1) まで、右または下のみ移動して到達する経路のうち、通過したセルの値の合計が最小となるものを求めます。
DP の定式化
dp[i][j] を「(i, j) まで到達する経路の最小値」とします。到達できる移元は上方向か左方向のみなので、次の漸化式が成り立ちます。
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
...
10月12日 23:10 投稿
ARC121E 解説: 包除原理と動的計画法を用いた解法
この問題は、「すべての要素が特定の条件を満たさない」ような場合の数え上げ問題であり、直接的に解くか、または「少なくとも1つの要素が条件を満たす」場合に包除原理を適用する方法があります。ここでは後者のアプローチを取ります。
(S(i)) を、「(i) 個の (k) について (a_k) が (k) に到達可能である」という条件を満たす順列の数と定義します。包除原理を使うと、以 ...
10月12日 23:04 投稿
ブロック分割による最小分散計算の最適化手法
与えられた n 個の連続ブロックを m グループに分割し、各グループの合計長さの分散を最小化する問題。最終出力は分散値に m² をかけた整数値とする。
分散 v の定義より、各グループ合計を rᵢ、その平均を r̄ とすると：
\[
v = \frac{1}{m} \sum_{i=1}^{m} (r_i - \bar{r})^2
\]
これを展開・整理すると、目的関数は以下のように変形可能：
\[
v \times m^2 = m \cdot \ ...
9月24日 23:19 投稿
競技プログラミングにおける問題解決戦略
数理的考察に基づくアルゴリズム設計について議論する。以下に代表的な問題パターンとその解法を示す。
「CF1183F Topforces Strikes Back」
最大値選択問題の最適化戦略を検討する。以下の条件を満たす組み合わせを探索する：
単一要素：最大値を選択
二要素：最大値の因数である必要がある
三要素：最大値とその約数の組み合わせ
証明概要
最大値以外の要素を含む場合 ...
9月22日 08:08 投稿
P7537 [COCI2016-2017#4] Rima（トライ木と木上の動的計画法）
P7537 [COCI2016-2017#4] Rima
トライ木と木上の動的計画法
問題の制約を整理すると、文字列の末尾に文字を追加したり、置換したり、削除したりできることが分かります。この操作は、あるポイントで削除が起こり、その後追加が続くため、単峰性を持ちます。両端の処理は対称なので、片側だけ考えれば十分です。文字列を逆転させてトライ木に挿入し、木上のDPで各ノードの部 ...
9月15日 19:50 投稿
競技プログラミングにおけるグラフ理論・組合せ数学・動的計画法の応用テクニック
弦なし閉路の検出と辺グラフ変換
長さ4以上の弦なし閉路を検出する問題では、頂点ベースの探索ではなく辺をノードとする線グラフへの変換が有効である。有向辺 $(u \to v)$ と $(v \to w)$ の間に、辺 $(u, w)$ が存在しない場合にのみ有向辺を張る。この変換により、元のグラフにおける三角形は新グラフで閉路を形成しなくなる。新グラフ上でDFSを実行し、最も深い返祖辺 ...
9月14日 12:35 投稿
AtCoder Beginner Contest 266 問題A-G 解説
A - Middle Letter
奇数長の文字列が与えられるので、その中央の文字を出力します。
#include <iostream>
#include <string>
#include <vector>
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::string input_str;
std::cin >> input_str;
// 0-indexedなので、長さLの文字列の中央は L/2
...
9月13日 12:05 投稿
リーコド核心的解析：雨水貯蔵とヒストグラム最大矩形の計算手法
問題 42：雨水貯蔵量のカウント
本問題は、与えられた非負整数配列において、各柱の間に貯まる雨水の総量を求めるものです。解決策には主に動的計画法と単調スタックを利用した方法があります。
動的計画法の活用
それぞれの柱の位置において、蓄積可能な水の高さは「その位置の左側にある最も高い柱」および「右側にある最も高い柱」の较小値によって決定されます。こ ...
9月12日 19:54 投稿
競技プログラミング模試解説：数論・文字列・区間クエリ処理
本記事では、CSP（中国情報オリンピック予選）直前に実施された模擬コンテストの4問について、解法と実装を解説する。
A. 素因数分解による数字列変換
各桁の数字を素因数に分解し、大きい素因数から順に出力する問題。例えば「6」は2×3なので、最終的な出力では「3」より「2」が先に来る必要がある。
各数字の素因数の個数を前計算し、7, 5, 3, 2の順に貪欲に出力する ...
9月4日 02:09 投稿