桁DPの基礎と応用
桁DPとは何か？
桁DP（Digit Dynamic Programming）は、通常ある区間[L, R]内で特定の制約を満たす数字の数を統計するために使用されます。LとRのデータ範囲が大きいため、DP（動的計画法）で統計する必要があることが多いです。
上限Rの処理テクニック
数値の比較ルールから、現在の桁の取りうる値の範囲は、前方の桁の値に依存することがわかります。
もし前方のすべて ...
6月25日 20:48 投稿
Codeforces 近況コンテストにおける高度なアルゴリズム技法と実装パターン
区間交差関係に基づく最小全域木構築
与えられた区間集合において、交差する区間同士を結ぶ辺の重みを権重の差とし、生成されるグラフの最小全域木を求める問題。辺を全列挙すると計算量が爆発するため、幾何学的性質と貪欲戦略を組み合わせる。権重が小さい区間から順にアクティブな集合に追加し、各区間の挿入・削除タイミング（スライン法）において、権重でソートされ ...
6月24日 18:37 投稿
USACO問題「Cow Exhibition」の動的計画法による解法
問題概要
n 個の要素があり、それぞれに整数値の属性 a と b が割り当てられています。いくつかの要素を選択して、選ばれた要素の a 属性の合計 と b 属性の合計 の総和を最大化したいと考えます。ただし、以下の条件を満たす必要があります：
a 属性の合計 ≥ 0
b 属性の合計 ≥ 0
この条件下で、(aの合計) + (bの合計) を最大にするプログラムを作成します。
アプロ ...
6月23日 20:37 投稿
プログラミング問題解法集
可能な限り簡潔にします。
CF679E
直接代入と修正のタイミングが正しいことがわかりますので、書き方について説明します。区間を良い数に変える操作を「加算」と呼びます。
既に区間代入が行われた区間にUpというマークを付けると、その区間とその子区間は1つの点と見なせます。そのため、修正の複雑さは単点修正と同じになります。
したがって、加算操作は次のように記述 ...
6月21日 23:23 投稿
動的計画法による最長共通部分列と最大部分和の解法
718. 最長共通部分配列の探索
2つの整数配列が与えられた場合、最長の共通部分配列の長さを求める問題です。部分配列は連続する要素から構成され、相対的な順序を保持する必要があります。
例：
入力：
配列A: [5, 8, 3, 7, 9]
配列B: [3, 7, 9, 4, 6]
出力：3
説明：最長共通部分配列は[3, 7, 9]
解法アプローチ
2次元DPテーブルを使用します。cache[i][j]は、配列Aの0～i ...
6月21日 16:32 投稿
競技プログラミングコンテスト問題解説：Codeforces Round 521 (Div. 3)
A. カエルのジャンプ
問題の条件に従って直接シミュレーションを行います。データ範囲に注意し、long long型を使用します。
void solve(){
long long a, b, k;
cin >> a >> b >> k;
cout n;
vector<int> arr(n);
for(int i = 0; i < n; i++) cin >> arr[i];
int result = 0;
for(int i = 0; i < n - 2; i++){
if(arr[i] = ...
6月19日 23:58 投稿
グラフ理論と行列操作アルゴリズム
100. 島の最大面積
与えられた1（陸地）と0（水）からなる行列において、島の最大面積を計算します。島は水平または垂直方向に隣接する陸地で構成され、周囲が水で囲まれているものとします。
from collections import deque
def max_area_of_island(grid):
rows, cols = len(grid), len(grid[0])
max_area = 0
for i in range(rows):
for j in ...
6月18日 17:18 投稿
動的計画法の基礎と実践 : フィボナッチ数、登り方問題、コスト最小化登り方問題
動的計画法（Dynamic Programming, DP）は、問題に多数の重複する部分問題がある場合に効果的な手法です。DPの各状態は前の状態から導き出されます。これは貪欲法とは異なり、貪欲法は部分的な最適解を選択します。
解法ステップ
dp配列（またはdpテーブル）とそのインデックスの意味を決定する。
再帰式（または推移式）を決定する。
dp配列の初期化を行う。
探索順序を ...
6月17日 23:36 投稿
傾き最適化DP：Luogu P2365とSDOI2012タスクスケジューリング問題の解法
問題文
動的計画法の問題を考察します。便宜上、問題文中の費用係数を\\(v_i\\)で表現します。
\\(f_i\\)を第\\(i\\�\\)位置までの最適解と定義します。各遷移は、\\(i\\)番目に区間\\([j+1,i]\\)のコストを追加する操作です。
明らかに、累和を用いて最適化できます。しかし\\(s\\)の存在により、直接次元を追加してグループ数を記録すると大きなオーバーヘッドが発生し ...
6月17日 17:27 投稿
文字列の最適削除と辞書順最小化アルゴリズム
各位置 i の文字を c[i] とし、canErase[x][y] を「文字 x が直後の文字 y を削除可能か」を表すブール配列とする。maxReach[i] は、位置 i から連続して削除可能な最大範囲の終端インデックスを示す（つまり、i+1 から maxReach[i] までの文字はすべて削除可能で、maxReach[i]+1 は削除不可能）。
貪欲戦略として、ある文字が自身の後続文字を削除でき、かつ自身も他の文 ...
6月11日 23:52 投稿