穴あきグリッドにおける有効な正方形の数え上げと動的計画法による最適化
$H \times W$ のグリッド上に $N$ 個の「穴（障害物）」が存在する際、穴を一切含まない正方形がいくつ存在するかを計算する問題は、動的計画法（DP）の典型的な応用例です。本記事では、この問題に対する直感的だが誤ったアプローチの分析と、それを修正した最適なアルゴリズムについて解説します。
誤ったアプローチ：独立した連続長に基づく累積和
まず考えられがちな ...
10月14日 09:16 投稿
C言語における二次元配列と文字配列の宣言・初期化・操作
二次元配列の基本概念
宣言とメモリ構造
C言語における二次元配列は、以下のような構文で宣言します。
データ型 配列名[行数][列数];
厳密には、C言語のメモリモデルにおいて真の多次元配列は存在せず、二次元配列は「一次元配列の要素として一次元配列を持つ」構造、すなわち連続したメモリブロックとして実装されています。
初期化の方法
一次元配列と同様に、二次元配 ...
9月21日 06:02 投稿
Javaにおける二次元配列の活用
二次元配列の基本
二次元配列は、一次元配列を要素として持つ配列であり、表形式のデータ構造として扱われます。行と列の概念を持ち、行列演算やゲームボードの管理など、複数の応用シーンで利用されます。
二次元配列の宣言方法
以下のようにして二次元配列を宣言および初期化できます。
// 行と列のサイズを指定
int[][] data = new int[3][4];
// 行ごとに列を個別 ...
9月10日 07:18 投稿
C言語での配列の基礎
1. 配列の概念
配列は、同じ型の要素の集合です。この定義には以下の2つの重要な点があります:
配列には1つ以上のデータを格納できますが、要素数は0にはなりません（変数を作成することは本質的にメモリ空間を確保することであり、要素数が0だとコンパイラがどの程度の空間を確保すべきかわかりません）。
配列に格納される複数のデータは同じ型である必 ...
8月8日 11:55 投稿
接頭和と差分配列の応用
接頭和 & 差分配列
計算量最適化のための基本技術
接頭和は複数回の区間クエリを高速化する手法。配列arr[N]に対してpre_sum[N]を構築し、
pre_sum[i] = pre_sum[i-1] + arr[i]と定義する。インデックスは1から始める必要がある。
実践問題
N都市を結ぶ道路があり、各セグメントの移動コストが与えられる。伝送装置を使って最大kセグメント飛躍可能。ただし1回の ...
7月24日 18:21 投稿
C++における二次元配列の実装と操作
二次元配列は、行と列の構造を持つデータ格納機構であり、C++では配列の配列として実現されます。この構造は行列的なデータ処理やゲーム開発、画像処理など、多次元データを扱う場面で広く利用されます。
宣言と初期化
二次元配列は、行数と列数を明示的に指定して宣言します。以下のように、静的サイズで宣言可能です：
int grid[5][8]; // 5行8列の整数配列
初期化は ...
5月14日 20:27 投稿