二分探索と自動機を用いた計算機構築
アプローチ
共通接尾辞の再帰的な構築。（実質は有限状態オートマトン）
直接力技を使う？二分木を作れば良いが、ノードが多すぎて無理。
しかし、多くの部分木が繰り返し利用されるため、共有すれば良い。詳細はコードで確認。
実装
verify_length 関数
void verify_length(int start, int end, int left, int right) {
int mid = (start + end) / 2;
if (start ...
6月12日 18:47 投稿
河川の岩場問題：二分探索による最適解
問題リンク
https://www.luogu.org/problemnew/show/P2678
問題背景
年一度の「岩場飛び」大会が開催されます！
問題説明
この大会は一直線の川で行われ、川の中には大きな岩が点在しています。主催者はすでに2つの岩をスタート地点とゴール地点として選定しました。スタートとゴールの間にはN個の岩（スタートとゴールを含まない）があります。競技中、参加者はスター ...
5月19日 12:57 投稿
配列内のピーク要素を対数時間で特定する二分探索アルゴリズムの実装
問題の定義と制約条件
隣接する要素よりも厳密に大きい値を「ピーク」と定義する。配列の両端（インデックス -1 および n）は負の無限大と見なせるため、配列内には必ず少なくとも1つのピークが存在することが数学的に保証されている。複数のピークが混在する可能性があるが、要件としていずれか1つのインデックスを返せば十分である。重要な制約として、線形探索ではなく ...
5月15日 04:44 投稿
2024年钉耙コーディング中国大学生アルゴリズム設計スーパーリーグ（1）
本稿では、2024年钉耙コーディング中国大学生アルゴリズム設計スーパーリーグ（1）から選出された数問の問題とその解法について説明する。
循環位移（Circular Shift）
HDU - 7433
アプローチ
文字列ハッシュを用いて、文字列Aを2回連結したAAを作成する。この文字列のハッシュ値を計算し、mapまたはsetに記録する。|A| ≤ |B| であるので、B中での長さ|A|のすべての部分文 ...
5月10日 23:24 投稿