動的計画法の核心：再帰関係の構築と理解
再帰関係の核心概念
再帰関係（または状態遷移方程式）とは、大きな問題をいくつかの部分問題に分解し、それらの部分問題の解を用いて大きな問題の解を導き出すための関係式です。DP配列の各要素は通常、特定の状態における問題の解を表し、再帰関係はこれらの状態間の変換方法を記述します。
再帰関係の特定手順
状態とその変化の分析：
問題 ...
6月10日 20:44 投稿
部分配列の絶対値和の最大値 (DP)
与えられた配列から、部分配列の和の絶対値の最大値を求めます。部分配列は空でも構いません。
方法1
最大部分配列の和と最小部分配列の和を別々に動的計画法で計算します。その後、これらの値の絶対値の最大値を求めます。
考え方
max_sum_ending_at[i]: nums[i]で終わる部分配列の中で最大の和
min_sum_ending_at[i]: nums[i]で終わる部分配列の中で最小の和
コード
co ...
6月7日 18:55 投稿
藍橋杯2021年省赛B組 C/C++ 問題解説
問題A：空間計算
メモリ空間の計算問題。256MBをバイト単位で表現し、各データが32ビット（4バイト）の場合の要素数を求める。
計算式：256 × 1024 × 1024 × 8 ÷ 32 = 67108864
問題B：カードの数字
0から9までの数字カードが各2021枚ずつある。1から順に数字を書いていくとき、何まで書けるかを求める問題。
#include <iostream>
using namespace std;
int main( ...
6月5日 23:06 投稿
牛客プログラミングコンテスト89 解法解説
A. 牛牛吃米粒
入力: 整数 n, k と符号なし整数 s、および k 個の位置 a_i。各ビット位置が制限されていないか検証し、s のビットが立っている位置が禁止領域と重なる場合は "NO"、それ以外は "YES" を出力。
#include <iostream>
#include <vector>
using namespace std;
int main() {
unsigned long long s;
int n, k;
cin >> n >> k;
vect ...
6月5日 22:18 投稿
2023年伝智杯プログラミング競技予選ソリューション
文字列連結
2つの文字列を入力として受け取り、連結して出力します。空白を含む可能性があるため、getline関数を使用します。
#include <iostream>
#include <string>
using namespace std;
int main() {
string a, b;
getline(cin, a);
getline(cin, b);
cout << a + b;
return 0;
}
最小差分値
整数配列内の隣接要素間の最小差 ...
6月4日 19:44 投稿
最長有効括弧の探索：スタックと動的計画法によるアプローチ
問題の説明：
'(' と ')' のみからなる文字列が与えられます。最長の有効な（形式が正しく連続している）括弧部分文字列の長さを見つけてください。
例 1：
入力：s = "(()"
出力：2
説明：最長の有効な括弧部分文字列は "()" です
例 2：
入力：s = ")()())"
出力：4
説明：最長の有効な括弧部分文字列は "()()" です
例 3：
入 ...
6月4日 17:25 投稿
Javaアルゴリズム速習ガイド
Javaアルゴリズムクイックリファレンス
リスト
初期化
List<Integer> 数値リスト = new ArrayList<>();
主なメソッド
add(Object 要素);
size();
get(int インデックス);
isEmpty();
contains(Object o);
remove(int インデックス);
マップ
マップはキーと値のペアを保持するコレクションです。
初期化
Map<String, Integer> マップ = new HashMap< ...
6月4日 16:11 投稿
連続部分列の最大和を求めるときの主要3つのアルゴリズム
整数配列から和が最大となる連続した部分配列（要素は1つ以上）を見つけ、その和を返す問題を取り上げます。配列内の任意の連続する区間の合計値のうち最大値を求める手法として、漸化式を用いた線形走査、累積和の差分最適化、そして分割統治法を解説します。
手法1：漸化式による線形走査（Kadaneのアルゴリズム変形）
あるインデックス i で終了する連続部分配列の最大 ...
6月3日 22:26 投稿
USACO 2021年オープンコンテスト金問題の解法アプローチ
問題1: 農場の統一された牛群
各要素の前後で最初に現れる同一要素の位置をprevおよびnext配列で管理します。区間[l, r]が有効となる条件は、next[l] > rかつprev[r] < lを満たすことです。
左端点lを固定し、右端点の有効性をセグメント木で管理します。prev[r] < lを満たすrを二重ポインタで追跡しながら、セグメント木の対応位置をインクリメントします。各lで ...
6月2日 17:58 投稿
回文部分文字列と回文部分列の動的計画法による解法
回文部分文字列のカウント
この問題の難しさは、DP配列の定義と漸化式の構築にあります。直接dp[i]を[0,i]の部分文字列に含まれる回文の数と定義すると、漸化式を見つけることができません。回文の性質を利用して、次のような漸化式を構築できます：[i,j]が回文かどうかを判断するために、s[i] == s[j]の場合は[i+1,j-1]が回文かどうかを確認するだけで済みます。s[i] != s ...
6月1日 11:09 投稿