部分文字列の一致判定と出現回数を数える動的計画法
LeetCode 392: 文字列の包含関係判定
文字列 s が文字列 t の部分列であるかを確認する問題では、動的計画法（DP）による状態管理が有効です。
DPテーブルによるアプローチ
配列 match[i][j] を「s の先頭 i 文字と t の先頭 j 文字を比較した際の、一致した文字列の最大長」と定義します。
s[i-1] == t[j-1] の場合：末尾同士が一致するため、直前の一致長に1を加算しま ...
7月21日 21:47 投稿
動的計画法に基づくアルゴリズム問題集と実装パターン
矩形分割問題
与えられた $N \times M$ の矩形を、縦または横に分割する操作を繰り返して特定の面積 $K$ を得るまでの最小コストを求める問題である。$N, M$ が小さいため、状態をメモ化する再帰関数を用いて分割位置を全探索するアプローチが有効である。各ステップで左右または上下に切り分け、分割線に沿ったコストを加算しながら再帰的に遷移する。
#include <iostr ...
7月21日 00:04 投稿
SMU Summer 2024 Contest Round 5
SMU Summer 2024 Contest Round 5
ロボット高橋君
思考プロセス
重み (W_i) でソートし、前後の 1 と 0 の個数を計算します。答えはおおよそ (\max(ans,pre_i+suf_{i+1})) の形式になります。
ソート後、(W_i = W_{i+1}) の場合、i と i+1 の間で分割できないため特別な処理が必要です。
コード
#include <iostream>
#include <vector>
#include <algorithm ...
7月20日 17:48 投稿
動的計画法の応用とコード実装
動的計画法の基本概念
動的計画法（Dynamic Programming、以下DP）は、問題を小さなサブ問題に分解し、その解を記憶して再利用することで効率的に解決するアルゴリズム手法です。この方法は、重複計算を回避し、時間効率を大幅に向上させます。
dp[k]：サブ問題の解を保持する配列
初期条件の設定
状態遷移方程式の導出
メモリ節約のためのローリング変数や配列の活用
...
7月19日 03:18 投稿
動的計画法における最長増加部分列モデル
動的計画法を用いた最長増加部分列（LIS）のアルゴリズムとその応用について解説します。最長増加部分列は、与えられた数列の中から単調に増加する部分列の中で最も長いものを求める問題です。このモデルは、様々な最適化問題に応用可能です。
最長増加部分列の基本概念
最長増加部分列問題は、与えられた数列において、各要素が前の要素よりも大きくなるように選んだ部分 ...
7月18日 19:13 投稿
二次元配列における最大部分行列和の計算
解法の概要
本課題は行列内の全ての部分行列の和の中で最大値を求めることを要求します。全ての部分行列を総当たりで列挙し和を計算する方法では、計算量がO(n^4)となり、nが大きい場合に効率が悪くなります。ここでは二次元累積和の技法を用いて計算プロセスを最適化します。
二次元累積和の基本概念
二次元累積和は前処理技術の一つで、任意の部分行列の和をO(1)時間 ...
7月17日 02:58 投稿
洛谷100題チャレンジ (5/100)
洛谷100題チャレンジ (5/100)
P1002 [NOIP2002 普及組] 馬避け - 洛谷 | コンピュータ科学教育新生態
long long型を使用しないと問題発生注意!!!
馬の制御点を全てマークし、残りは通常通り转移すればよい
\(dp[i][j] += dp[i - 1][j] + dp[i][j - 1]\)
\(i=0||j=0\)の場合、左または上からのみ转移可能
using i64 = long long;
using namespace std;
typedef pair Pair ...
7月16日 23:20 投稿
木の直径を求める2つの主要アプローチ
木の直径（Tree Diameter）とは、木構造グラフにおいて最も離れた2つのノード間の距離を指します。この計算には、主に深さ優先探索（DFS）を2回行う方法と、動的計画法（DP）を用いる方法の2つが広く知られています。本記事では、それぞれのアルゴリズムの原理と実装手法について解説します。
DFSによる2回の探索アプローチ
この手法は非常に直感的で、計算量も効率的です ...
7月14日 23:27 投稿
2023年10月25日 模擬試験の反省
時間管理
7:40 から 8:40 まで、対拍と乱数生成の準備を行い、問題を読み込み、T1 を開始しました。40分で初回の提出を完了し、対拍で小さな誤りを見つけたため修正して再提出しました。
8:40 から 10:20 まで、T2 の解決に取り組みました。以前の模擬試験の T2 と類似点がありましたが、直接的な解法が見つからなかったため、まずは暴力解法を考えました。しかし、n ≤ 6 ...
7月14日 20:38 投稿
Pythonによるアルゴリズム実装入門
基礎構文とデータ構造
1. 変数と基本操作
Two Sum（二数の和）
# アプローチ1：全探索
class Solution:
def twoSum(self, nums, target):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
# アプローチ2：ハッシュマップ
class Solution: ...
7月13日 00:57 投稿