ブロック分割による最小分散計算の最適化手法
与えられた 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 投稿
USACO13OPEN Photo G の解説
序文
問題のリンク：洛谷。
問題概要
長さが \(n\) の配列があり、一部の要素はすでに色が塗られています。\(m\) 個の制約が与えられ、それぞれ \(l_i \sim r_i\) の範囲内にちょうど1つの要素が色付きであることを示します。この制約をすべて満たすように、最大で何個の要素を色付けできるかを求めます。
\(n \leq 2 \times 10^5\)，\(m \leq 10^5\)。
問題解析
解法 \(1\ ...
8月15日 23:59 投稿
C言語によるLeetCode 1047と239の実装解説：スタック処理と単調キュー最適化
問題 1047: 隣接する重複文字の完全除去
問題定義
英小文字のみで構成される文字列が引数として渡されます。この文字列に対して、「隣接する同一文字をペアで取り除く」という演算を繰り返し適用します。すべての演算が行き詰まった時点で残っている文字列を返却してください。解答は一意に決まります。
入力例: "abbaca" → 出力: "ca"
制約条件: 文字列長は [1, 20000] ...
7月5日 22:28 投稿
基環樹構造上の動的計画法：アルゴリズム設計と実装手法
基環樹の定義と構造的特徴
基環樹（Base Ring Tree）とは、ノード数と辺数が等しく、かつ連結なグラフ構造を指します。その最大の特徴は、グラフ内に閉路（サイクル）がちょうど一つだけ存在することです。グラフが非連結であり、各連結成分がノード数と辺数を一致させる場合は「基環樹森」と分類されます。通常の木構造を対象とした動的計画法（木DP）と比較すると、閉路 ...
5月13日 16:44 投稿