最長増加部分列の効率的解法：貪欲法と二分探索
動的計画法から最適解への転換
最長増加部分列(LIS)問題では、無秩序な配列から厳密に増加する最長の部分列を見つける。例えば配列[10,9,2,5,3,7,101,18]では、LISは[2,3,7,101]で長さ4となる。
動的計画法の基本アプローチ
基本解法は動的計画法(DP)によるO(n²)の実装：
def lis_length_dp(nums):
dp = [1] * len(nums)
for i in range(1, len(nums)):
f ...
7月6日 22:08 投稿
プログラミングにおける時間制御技術：タイムリミット回避戦略
プログラミングにおける時間制御技術
背景
時折、私たちの検索処理は非常に長時間かかり、タイムリミットエラー（TLE）が発生します。TLEが発生した場合のスコアは0ですが、タイムリミット直前に現在の最適解を出力できれば、スコアは0以上となります。このような状況では、時間制御技術が必要になります。
時間制御とは
時間制御、その名が示す通り、時間を制御するこ ...
7月6日 00:29 投稿
Binary Indexed Tree の基礎と応用
概要
Binary Indexed Tree（BIT）は、単点更新と区間クエリを効率的に処理できるデータ構造です。計算量 O(log N) で操作を実行可能であり、競技プログラミングやアルゴリズム最適化で広く利用されます。
構造と原理
BIT は 2 進数表現に基づく構造を利用します。任意の整数は複数の 2 のべき乗和で表せることから、配列要素をべき乗区間で管理します。lowbit 演算（x & - ...
6月25日 18:51 投稿
行列高速累乗による線形漸化式の効率的解法
線形漸化式（例：フィボナッチ数列）を単純に計算すると、nが10⁸を超えると時間がかかりすぎます。これを解決するのが「行列高速累乗」です。この手法は、二進展開と行列乗算を組み合わせ、計算量をO(log n)まで削減します。
基礎知識：二進高速累乗
整数のべき乗を高速に計算するアルゴリズムです。指数を二進数で分解し、繰り返し二乗しながら結果を構築します。
long l ...
6月24日 01:05 投稿
動的計画法による最長共通部分列と最大部分和の解法
718. 最長共通部分配列の探索
2つの整数配列が与えられた場合、最長の共通部分配列の長さを求める問題です。部分配列は連続する要素から構成され、相対的な順序を保持する必要があります。
例：
入力：
配列A: [5, 8, 3, 7, 9]
配列B: [3, 7, 9, 4, 6]
出力：3
説明：最長共通部分配列は[3, 7, 9]
解法アプローチ
2次元DPテーブルを使用します。cache[i][j]は、配列Aの0～i ...
6月21日 16:32 投稿
Manacherアルゴリズムによる最長回文部分文字列の効率的探索
問題の定義
与えられた文字列から、連続する部分文字列の中で最も長い回文（前後どちらから読んでも同じになる文字列）を求める問題を「最長回文部分文字列問題」と呼ぶ。例えば文字列 "aaaba" では、"aaa" や "aba" が回文であり、その中で最長のものは "aaa" となる。
この問題は動的計画法でも解けるが、時間計算量が O(n²) となる。それに対して Manacher アルゴリズム ...
6月19日 21:07 投稿
アルゴリズムとデータ構造8 - 線形篩による一般乗法関数の計算
概要
競技プログラミングの問題を解く中で、線形篩を用いた一般乗法関数の計算方法を学んだので、その説明を行う。
前提知識
乗法的関数：任意の互いに素な整数p,qについてf(p)×f(q)=f(pq)を満たす関数。
完全乗法的関数：任意の整数p,qについてf(p)×f(q)=f(pq)を満たす関数。
線形篩：O(n)でn以下の素数を列挙するアルゴリズム。
適用範囲
任意の素数pに対して、f(p)およ ...
6月10日 19:05 投稿
ビット演算の核心技術：基礎から実践まで（C++による実装）
アルゴリズムの効率性を最大化するためのビット演算の体系的な解説。状態圧縮やマスク操作、空間複雑度O(1)の最適化手法を、大手企業の実際問題を通じて学習します。
一、ビット演算子の基本操作
演算名
記号
動作
応用例
論理積
&
共に1のときのみ1
フラグの抽出
論理和
|
いずれか1なら1
設定値の統合
排他的論理和
^
異なるビットが1
重複値の除去
...
5月27日 11:03 投稿
KMPアルゴリズムにおけるnext配列の最適化手法
KMPアルゴリズムのnext配列最適化
KMP（Knuth-Morris-Pratt）アルゴリズムでは、パターン文字列の部分一致情報を格納したnext配列を用いて、主文字列との照合時に不要な比較をスキップする。しかし、標準的なnext配列には冗長な比較が含まれる場合があるため、これをさらに最適化することが可能である。
最適化が必要なケース1
例えば、パターン文字列の先頭文字と現在の ...
5月26日 08:16 投稿