樹における最近共通祖先の効率的計算手法
木構造上の2頂点間の最近共通祖先（Lowest Common Ancestor, LCA）を高速に求めるには、複数のアルゴリズムが存在します。本稿では、倍増法、オイラー巡回＋RMQ、および木の重軽分解（Heavy-Light Decomposition）の3つの代表的手法について、それぞれの設計思想・実装構造・計算量特性を解説します。
倍増法によるLCAクエリ
各頂点から根方向へ2kステップ先の祖先とその ...
8月5日 03:47 投稿
ABC367 回顾：典型アルゴリズム問題の解法と実装
A問題: 時間帯の重なり判定
この問題は、ある時間が指定された時間範囲に含まれるかを判定するものである。注意点として、時間帯が翌日にまたがるケースがある。これを処理するために、終了時刻が開始時刻より小さい場合は終了時刻に24を加算し、範囲を正しく表現する。
次に、基準となる時刻（国王が叫ぶ時刻）がその範囲内にあるか、または24時間を加えたバージョンが範 ...
7月3日 23:27 投稿