Pythonリストの基礎と操作
1. リストとは
Pythonにおけるリストは、複数の要素を格納するためのデータ構造です。リストは変更可能であり、異なる型の要素を含めることができ、インデックスを使用して要素にアクセスしたり修正したりすることができます。
リストは角括弧「[]」で定義され、各要素はカンマで区切られます。
リストの要素には整数、浮点数、文字列、ブール値、さらには他のリストなど、 ...
10月11日 20:41 投稿
C言語で連鎖リストの実装
連鎖リストの概念と構造
連鎖リストは物理的に非連続で順序が保たれていないデータ構造であり、論理的な順序は各ノード間のポインタリンクによって実現されます。
連鎖リストの分類
実際のアプリケーションでは様々な種類の連鎖リストがありますが、主に以下の3つの特性を組み合わせることで8種類の構造が考えられます：
単方向または双方向
ヘッダありまたはヘッダなし
...
10月8日 12:21 投稿
セグメントツリーの応用と実装
セグメントツリーの基本構造と操作
セグメントツリーは、範囲クエリや更新操作を効率的に行うためのデータ構造です。以下では、いくつかの問題に対してセグメントツリーをどのように適用するかを説明します。
#include
using namespace std;
#define FOR(i, a, b) for (int i = (a); i = (b); --i)
#define DEBUG(x) cerr > x >> y;
if (type == 1) {
...
10月8日 04:38 投稿
二分探索木における指定値和の検出アルゴリズム
二分探索木（BST）のルートノードと整数目標値が与えられた場合、木内に和が目標値と等しくなる2つの異なるノードが存在するかを判定する手法について解説します。この課題は、木構造の走査戦略と中間データ保存形式の変更によって計算効率を大幅に改善できます。
基本手法：全要素収集後の線形照合
最初に樹形構造を平坦化し、すべてのノード値をリストへ格納します。その ...
10月7日 23:15 投稿
動的配列を用いた連絡先管理システムの設計と実装
データ構造の基本：線形リストとその応用
現代のソフトウェア開発において、データを効率的に管理するための手法は不可欠です。特に、一連の要素を順序立てて扱う必要がある場合、線形データ構造が広く利用されます。代表的な例として、配列に基づく動的配列（Dynamic Array）があり、これはC言語でのメモリ管理を活かして柔軟なデータ格納を実現します。
線形リストの特 ...
10月4日 02:13 投稿
配列と集合の問題解説: Codeforces Round 932 (Div. 2)
C. メッセンジャープログラム
2つの配列aとb、および整数Lが与えられます。aとbのインデックスのシーケンスpを見つけて、\(\sum a_{p_i} + \sum |b_{p_i}-b_{p_{i+1}}| \leq L\)を満たす必要があります。
解法
キー1：bを昇順にソートすることが最適です。
キー2：固定された\(b_l\)と\(b_r\)に対して、\(\sum^r_l |b_{p_i}-b_{p_{i+1}}| = b_r - b_l\)となり、これは固定 ...
9月28日 13:57 投稿
配列に対するブロック分割データ構造とその応用
本稿では、配列ベースのデータ構造におけるブロック分割（Block Decomposition）の概念と、様々な問題への応用について解説します。ブロック分割は、配列を一定サイズの小ブロックに分割し、各ブロックに対して集約情報や遅延更新メカニズムを導入することで、区間操作や点操作の計算量をバランス良く最適化する手法です。
ブロック分割の基本
配列を長さ約 \\(B\\) のブ ...
9月18日 09:56 投稿
P7537 [COCI2016-2017#4] Rima（トライ木と木上の動的計画法）
P7537 [COCI2016-2017#4] Rima
トライ木と木上の動的計画法
問題の制約を整理すると、文字列の末尾に文字を追加したり、置換したり、削除したりできることが分かります。この操作は、あるポイントで削除が起こり、その後追加が続くため、単峰性を持ちます。両端の処理は対称なので、片側だけ考えれば十分です。文字列を逆転させてトライ木に挿入し、木上のDPで各ノードの部 ...
9月15日 19:50 投稿
データ構造詳解：木構造と二分木の理論から実装まで
木構造の基礎概念
定義と特徴
木構造は、再帰的に定義される階層型データ構造です。要素数が n (n ≥ 0) の有限集合であり、n = 0 の場合は空木と呼ばれます。非空木において以下の条件を満たします：
根ノードは唯一存在し、前駆ノードを持ちません。
根以外の子ノードは、互いに素な部分木として分類され、各ノードは厳密に1つの親を持ちます。
各ノードは0個以上の後続 ...
9月14日 19:37 投稿
二分探索木における最小絶対差と最頻値、および二分木の共通祖先探索アルゴリズム
1. 二分探索木における最小絶対差の取得
二分探索木（BST）の性質として、中序巡回（In-order Traversal）を行うと、ノードの値を昇順で取得できるという特徴があります。この性質を利用することで、隣接するノード間の差分を比較し、最小絶対差を効率的に求めることが可能です。
ポインタ prevNode を使用して、常に現在のノード currNode の直前の値を保持するこ ...
9月14日 13:56 投稿