木構造における動的計画法（Tree DP）の基礎と典型問題
木構造と動的計画法の親和性
木（Tree）は再帰的に定義されるデータ構造であり、部分問題に分割して解く動的計画法（DP）と非常に相性が良いです。本稿では、木構造におけるDPの典型的な問題と、その状態遷移および実装について解説します。
グラフ理論における4つの典型問題
一般のグラフにおいて、以下の4つの問題はNP困難またはco-NP完全として知られていますが、木構 ...
10月16日 09:20 投稿
株式取引・配列操作・文字列生成におけるアルゴリズム実装ガイド
アルゴリズム設計において、状態遷移・貪欲選択・単調性・深さ優先探索の4つのパターンは頻出テーマです。以下にそれぞれの典型問題に対する実装手法と、構造化されたコード例を示します。
1. 取引手数料を含む株式利益の最大化
本問題は、状態を「保有中」と「未保有」に分類し、日次で利益が最大化される経路を追跡します。動的計画法を用いる場合、直前の状態から現在 ...
10月5日 05:38 投稿
Educational Codeforces Round 165 (Rated for Div. 2) 解説：各問題のアルゴリズム設計と実装パターン
問題A: 双方向関係の検出
与えられた順列pにおいて、異なるインデックスi, jが互いを参照し合っているか（つまり p[i] = j 且つ p[j] = i）を判定する。そのようなペアが存在する場合、必要な選択肢の数は2であり、存在しない場合は必ず3必要となる。全探索ではなく配列への直接アクセスにより、線形時間でこの条件を満たすかどうかをチェックできる。
#include <iostre ...
9月13日 04:41 投稿
動的計画法（DP）における時間計算量と空間計算量の評価手法
1. 計算量評価の基本モデル
動的計画法（DP）の計算量を正確に見積もるためには、アルゴリズムを以下の3つの要素に分解して考えます。
状態（State）： dp[i] や dp[i][j] と定義される、部分問題の解を保持する変数。
状態の総数： 計算が必要なすべての部分問題の数（1次元DPなら $n$、2次元DPなら $n \times m$ など）。
遷移コスト： 1つの状態（例：dp ...
8月11日 09:02 投稿
動的計画法による部分列問題の徹底攻略：1次元・2次元、連続・非連続の各パターン
1. 不相交の線 (LeetCode 1035)
この問題は、一見すると幾何学的な制約があるように見えますが、本質的には「最長共通部分列 (LCS)」を求める問題と同じです。2つの配列間で線を引く際に交差させないという条件は、選ぶ要素の相対的な順序を維持することを意味します。
アルゴリズムの定義
dp[i][j] を、配列 data1 の最初の i 個の要素と、配列 data2 の最初の j 個の要 ...
7月7日 17:15 投稿
AtCoder Beginner Contest 358 全問題アプローチと実装例
A - Welcome to AtCoder Land
この問題では、入力された二つの文字列が特定の値と完全に一致するかを確認する基本的な処理が必要です。
実装ロジック
標準入力で受け取ったストリングスを入力変数へ保存し、固定されたターゲット文字列と比較します。両方が一致した場合のみ「Yes」を出力し、それ以外の場合は「No」を返却します。
#include <iostream>
#include & ...
5月17日 12:18 投稿