アルゴリズム競技向け：シミュレーション・ビット演算・ハッシュ最適化の実践
本記事では、代表的なアルゴリズム問題を題材に、配列走査、プレフィックス和、ビット操作、ハッシュマップによる高速化の4つの核心技術を解説します。各問題は段階的に難易度が上がり、実装の背景にある設計思想と数学的洞察を重視して解説します。
1. 中央要素の条件判定（初級）
整数配列 a が与えられる。インデックス i（先頭と末尾を除く）について、a[i] ≥ a[i-1] ...
10月4日 07:33 投稿
プレフィックス和と差分アルゴリズムの理解とC++実装
プレフィックス和アルゴリズム
基本概念
プレフィックス和は配列処理技術の一種で、事前計算により部分区間の和をO(1)で取得可能にします。入力配列をdataとすると、プレフィックス配列prefは次のように定義されます：
pref[i] = data[0] + data[1] + ... + data[i]
pref[0] = data[0]
構築方法
C++による実装例：
vector<int> constructPrefixArray(const vector& ...
5月21日 01:20 投稿