01ナップサック問題とその解法
ナップサック問題の概要
基本的な解決策
方法一：二次元配列を使用した01ナップサック問題
dp配列の定義
再帰式の決定
dp配列の初期化
ループ処理
import java.util.*;
public class ItemManager {
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
int itemCount = reader.nextInt();
int capacit ...
7月8日 22:25 投稿
動的計画法によるナップサック問題と等和分割問題の解法
46.研究材料の持ち運び問題
動的計画法を用いたナップサック問題の解法について解説する。`dp`配列を定義し、`dp[i][j]`はi個の物品をjの容量で運ぶ際の最大価値を表す。漸化式は以下の2つのケースに分けられる：
1. 物品を入れられる場合：`dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])`
2. 物品を入れられない場合：`dp[i][j] = dp[i-1][j]`
初期化処 ...
7月8日 20:21 投稿
最長増加部分列の効率的解法：貪欲法と二分探索
動的計画法から最適解への転換
最長増加部分列(LIS)問題では、無秩序な配列から厳密に増加する最長の部分列を見つける。例えば配列[10,9,2,5,3,7,101,18]では、LISは[2,3,7,101]で長さ4となる。
動的計画法の基本アプローチ
基本解法は動的計画法(DP)によるO(n²)の実装：
def lis_length_dp(nums):
dp = [1] * len(nums)
for i in range(1, len(nums)):
f ...
7月6日 22:08 投稿
動的計画法入門：フィボナッチ数列モデル
動的計画法（DP）とは
動的計画法（Dynamic Programming, DP）は、問題をより小さな部分問題に分割し、その結果を再利用することで効率的に解く手法です。特に「重複部分問題」と「最適部分構造」を持つ問題に有効です。
DPの一般的な手順
状態の定義：DPテーブル（dp配列）の各インデックスが何を表すかを決める。これがすべての基盤となる。
状態遷移式：dp[i]を求める ...
7月2日 22:04 投稿
桁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 投稿