異端開発室

1. 計算量評価の基本モデル 動的計画法（DP）の計算量を正確に見積もるためには、アルゴリズムを以下の3つの要素に分解して考えます。 状態（State）： dp[i] や dp[i][j] と定義される、部分問題の解を保持する変数。 状態の総数： 計算が必要なすべての部分問題の数（1次元DPなら $n$、2次元DPなら $n \times m$ など）。 遷移コスト： 1つの状態（例：dp ...

線形探索によるアプローチ 最初に、最も単純な解法である線形探索（総当たり）について検討します。この手法では、配列の先頭から順に各要素を確認し、目的の値と一致するインデックスを返します。 def linear_search(data_array, search_val): for i in range(len(data_array)): if data_array[i] == search_val: return i return -1 このア ...

後綴配列（Suffix Array, SA）は、ある文字列のすべての接尾辞（Suffix）を辞書順に並べた配列です。高度な文字列処理において、接尾辞木（Suffix Tree）の代替として、より省メモリで実装しやすいデータ構造として広く利用されます。 基本定義 SA[i]: 全ての接尾辞を辞書順にソートしたとき、第 $i$ 位となる接尾辞の開始位置。 Rank[i]: 位置 $i$ から始まる接 ...

二分探索樹の基本原理 二分探索樹（Binary Search Tree）は、効率的なデータ検索を可能にする階層型のデータ構造です。この構造は以下の規則に従ってノードが配置されます。 左部分木: 親ノードよりも小さい値を持つ全てのノードが含まれます。 右部分木: 親ノードよりも大きい値を持つ全てのノードが含まれます。 再帰的性質: 各部分木自体もまた有効な二分探索樹でなけ ...

オブジェクトの深い複製手法 JSON変換による方法 const original = { data: [1, 2, { value: 3 }] }; const duplicated = JSON.parse(JSON.stringify(original)); 再帰関数を用いた実装 function createDeepCopy(source) { if (!source || typeof source !== 'object') return source; const result = Array.isArray(source) ? [] : {}; for (const prop in s ...

Java の設計思想とエディション Java 言語は、「一度記述すればどこでも実行可能（Write Once, Run Anywhere）」を理念として設計されています。主な特徴として、オブジェクト指向に基づく構造、高い可移植性、ガベージコレクションによるメモリ管理、そして堅牢なセキュリティ機構が挙げられます。また、マルチスレッド処理をネイティブにサポートしており、分散システム ...

本記事では、CodeForces 85D - Sum of Medians という問題に対する4つの異なる解法を解説します。この問題は、動的な集合に対する要素の追加、削除、および特定の位置にある要素の総和を求めるクエリを効率的に処理することを求めています。 問題概要 空の集合 S に対して、Q 個のクエリが与えられます。各クエリは以下の3種類のいずれかです。 add x: x \in [1, 10^9] ...

Redisでは、C言語標準の文字列（char*）を拡張した独自の動的文字列ライブラリ「SDS (Simple Dynamic Strings)」を採用しています。主なソースコードは sds.h と sds.c に実装されています。 1. SDSのデータ構造 SDSは、文字列の長さに応じて複数のヘッダー構造体を使い分け、メモリ使用量を最適化しています。 typedef char *sds; /* 構造体のパディングを無効化し、 ...