異端開発室

FHQ-Treap（または無旋Treap）は、ノードの回転操作を行わずに「分割」と「併合」という2つのプリミティブな操作のみを用いてバランスを維持する二分探索木です。このデータ構造は、各ノードに「値」と「ランダムな優先度」を持たせます。値は二分探索木の性質（左の子 < 親 < 右の子）を満たし、優先度はヒープの性質（親が子よりも高い優先度を持つ）を満たすよう ...

単調スタックの基本概念 単調スタック（Monotonic Stack）は、スタック内の要素が常に単調増加、または単調減少の順序を保つように維持するデータ構造です。この特性を利用することで、配列内の各要素に対して「左側または右側で最も近い、より大きい（または小さい）要素」を効率的に探索することができます。 典型的な応用としては、以下の 4 つのパターンがあります。 ...

1. スコア判定プログラム 成績評価を行う関数を実装します。switch文を利用してスコアの階級分けを行います。 #include <stdio.h> char get_grade(int score) { switch (score / 10) { case 10: case 9: return 'A'; case 8: return 'B'; case 7: return 'C'; case 6: return 'D'; default: return 'F'; } } int ...

ハッシュテーブルの仕組みと実装 基本構造の構築 ハッシュ値の生成手法は一旦置き、ハッシュ値が外部から与えられる前提でハッシュテーブルの骨組みを実装する。内部では配列と連結リストを用いてキーと値のペアを管理する。 public class CustomHashMap { static class Node { int code; Object key; Object val; Node next; ...

スプレイ木の概要 スプレイ木は、動的データ構造の一種であり、二叉探索木のバランスを保つための手法です。Daniel Sleator と Robert Tarjan によって提案されました。その特徴として、明示的なバランス操作を行わずとも、アクセスパターンの履歴に基づいて自動的に調整が行われる点が挙げられます。 この構造では、最近参照された要素を根へと移動させる「スプレイ」操作 ...

問題 Unixスタイルの絶対パス（'/'で始まる文字列）が与えられた場合、それを簡略化された標準パスに変換してください。 Unixファイルシステムでは、ドット（.）は現在のディレクトリを表し、2つのドット（..）は親ディレクトリ（1レベル上）に移動を表します。これらは両方とも、相対パスの一部として使用できます。複数の連続するスラッシュ（'//'）は、単一のスラッシュ ...

アルゴリズムの効率性を評価する指標 プログラムの品質を評価する際、コードの可読性や簡潔さだけでなく、「実行効率」が極めて重要な要素となります。アルゴリズムの効率性は、主に以下の2つの観点から測定されます。 時間計算量（Time Complexity）： アルゴリズムが実行を完了するまでにかかる時間の目安。 空間計算量（Space Complexity）： アルゴリズムが実 ...

1、非破壊シーケンスアルゴリズム これらのアルゴリズムは操作対象のコンテナ内の要素を変更しません。 1.1 find と find_if find(begin, end, value)：value に等しい最初の要素を検索し、イテレータを返す（見つからない場合は end を返す）。 find_if(begin, end, predicate)：述語を満たす最初の要素を検索する。 find_end(begin, end, sub_begin, sub_end)：サブシー ...

C. Anya and 1100 問題URL Problem - C - Codeforces 解法 文字列中の特定のパターン「1100」の出現回数を管理する問題です。ある位置の文字を変更したとき、それが「1100」の存在にどのような影響を与えるかを考えます。 変更による影響は三種類あります： 「1100」の個数が1増える 「1100」の個数が1減る 変化なし 変更箇所について、それが「1100」のどの位置（1 ...

Gorgeous Sequence: 区間最小値更新・区間最大値・区間和 長さ \(n\) の数列に対して次の操作をサポートする： 0 l r v: 区間 \([l, r]\) の要素を \(v\) との最小値で更新 1 l r: 区間の最大値を取得 2 l r: 区間の和を取得 各ノードで最大値・最大値の出現回数・二番目の最大値を管理。更新時： \(mx \leq v\): 処理不要 \(smx < v < mx\): 最大値のみ更新 \(v ...