グラフ理論と行列操作アルゴリズム
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 投稿
動的計画法の核心：再帰関係の構築と理解
再帰関係の核心概念
再帰関係（または状態遷移方程式）とは、大きな問題をいくつかの部分問題に分解し、それらの部分問題の解を用いて大きな問題の解を導き出すための関係式です。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 投稿