アルゴリズム実践トレーニングカリキュラム
配列操作編
二分探索と要素削除
二分探索：境界条件の2つの実装方法に注意。rightの定義、if条件と境界更新ロジックが重要。
左閉右閉左閉右開
rightの定義len(arr) - 1len(arr)
ループ条件while left <= right:while left < right:
境界更新right = mid - 1right = mid
class Solution:
def binary_search(self, arr: List[int], target: int) -> int:
...
6月26日 18:36 投稿
2023 年度 HDU マルチスクールコンテスト ラウンド 5 完全解答
本稿では、2023 年に開催された HDU 主催の大学生向け競技プログラミング大会（マルチスクール）第 5 回の各問に対するアルゴリズム解説と参考実装を示します。
A. タイフーン接近距離
問題概要
n 個の点によって構成される折線があり、q 回のクエリにおいて指定された座標からこの折線までの最短距離を計算する必要がある。データサイズは n, q ≤ 10^4 程度である。
解 ...
6月22日 20:42 投稿
Codeforces Round #1058 (Div. 2) 問題解説
A - MEX Partition
この問題の核心は、配列全体のMEX（Minimum Excluded Value）を求めることに帰着します。与えられた配列 $A$ をいくつかの部分集合に分割し、そのすべての部分集合のMEXが等しくなるための条件を考えます。
$A$ のMEXを $m$ とします。$m$ は $A$ に含まれない最小の非負整数であるため、$m$ より大きい要素は各部分集合のMEX計算において無視できま ...
6月21日 21:20 投稿
AtCoder Beginner Contest 366 の問題解説と実装
はじめに
今回のコンテストでは問題Eに大部分の時間を費やすことになり、残り15分でようやく正解にたどり着くという危ない場面でした。緑色レベルの問題にも苦戦するようでは、まだまだ実力不足を感じます。
A - Election 2
高橋君と青木君のどちらかが過半数の票を獲得したかどうかを判定するシンプルな問題です。
#include <iostream>
using namespace std; ...
6月4日 17:22 投稿
FHQ-Treapの詳細と実装：分割と併合によるランダム化平衡二分探索木
FHQ-Treap（または無旋Treap）は、ノードの回転操作を行わずに「分割」と「併合」という2つのプリミティブな操作のみを用いてバランスを維持する二分探索木です。このデータ構造は、各ノードに「値」と「ランダムな優先度」を持たせます。値は二分探索木の性質（左の子 < 親 < 右の子）を満たし、優先度はヒープの性質（親が子よりも高い優先度を持つ）を満たすよう ...
5月26日 10:16 投稿
アルゴリズムの計算量：時間計算量と空間計算量の基礎
アルゴリズムの効率性を評価する指標
プログラムの品質を評価する際、コードの可読性や簡潔さだけでなく、「実行効率」が極めて重要な要素となります。アルゴリズムの効率性は、主に以下の2つの観点から測定されます。
時間計算量（Time Complexity）： アルゴリズムが実行を完了するまでにかかる時間の目安。
空間計算量（Space Complexity）： アルゴリズムが実 ...
5月20日 06:10 投稿
イテレータパターンの詳細と実装例
イテレータパターンとは
イテレータパターン（Iterator Pattern）は、コレクションオブジェクトの内部構造を公開することなく、その要素に順次アクセスするためのインターフェースを提供する振る舞いに関するデザインパターンです。このパターンは、集合体（Aggregate）の走査処理をイテレータ（Iterator）という別のオブジェクトに委譲することで、クライアントコードから ...
5月17日 07:09 投稿
循環配列における次の大きな要素の検出と「雨水を貯める」問題のアルゴリズム解説
503. 循環配列における次の大きな要素 II (Next Greater Element II)
循環配列（最後の要素の次が最初の要素となる配列）が与えられた場合、各要素に対して「次に大きい要素」を見つける問題です。要素xの次に大きい要素とは、配列を巡回順で走査した際、xの後に現れる最初のxより大きな数値を指します。そのような数値が存在しない場合は-1を出力します。
解法アプロー ...
5月16日 17:53 投稿