異端開発室

木の連鎖分解（ヘビーライト分解）のまとめ 基本概念 基本的な考え方 実装手順 ステップ1: 重い子、重い連鎖 ステップ2: dfn順序 ステップ3: 時間計算量の分析 コード実装 重い子の検出 連鎖分解 各種操作 LCAの計算： パス更新： パスクエリ： 推奨問題 基本概念 基本的な考え方 \qquad 木の連鎖分解、名前の通り、木データ構造に適用され ...

2つの数の合計が特定の値になる場合 配列がソートされている場合、双指針法を用いて効率的に解決できます。左端と右端から開始し、合計値を比較してポインタを移動します。 public class SumSolution { public static int[] findTwoSum(int[] arr, int target) { int start = 0; int end = arr.length - 1; while (start < end) { ...

二分木の基礎理論 二分木は各ノードの子ノード数が最大2の木構造です。主要な形態として完全二分木と完全二分木が存在します。データ格納方式には配列を用いた順序格納とポインタを用いたリンク方式があります。走査方法は以下の通りです： 先行走査（深さ優先） 中間走査（深さ優先） 後行走査（深さ優先） 階層走査（幅優先） class BinaryNode: def __init__(self ...

A. 二分探索の学習 基本的な二分探索アルゴリズムを実装する問題です。指定された範囲内でターゲット値を見つけるために必要なステップ数を計算します。 #include <iostream> #include <vector> #include <algorithm> using namespace std; int binary_search_steps(int left, int right, int target) { int steps = 0; while (left <= r ...

問題概要 LeetCodeの問題593では、2次元平面上の4点の座標が与えられ、それらが正方形を形成するかどうかを判定する必要がある。入力される点の順序は任意である。 解法の考え方 ベクトル演算を利用することで効率的に解決できる。基準点を1つ選び、他の3点へのベクトルを計算する。これらのベクトルを長さの昇順に並べ替え、\(\boldsymbol{v}_0, \boldsymbol{v}_1, \bolds ...

目次- ブルートフォース法 (1) ブルートフォース法 (2) 重量値セグメント木 演習問題 はじめに主席木を学習中に、重量値セグメント木の学習ノートを更新しておくのを思い出しました まず、以下の問題を考えてみましょう： 配列に対して以下の操作を行います： 操作 (1)：配列中の第k小さい要素を問い合せます（答えは存在すると仮定）。 操作 (2)：ある要素を変更しま ...

バブルソート 隣接要素を比較して交換するアルゴリズム。最大値を末尾に移動させる処理を繰り返す。 public class BubbleSort { public static void executeSort(int[] array) { int length = array.length; for (int i = 0; i < length - 1; i++) { for (int j = 0; j < length - 1 - i; j++) { if (array[j] > array[j ...

C++の標準ライブラリは、効率的なデータ操作を支援する多くのアルゴリズムを提供しています。これらのアルゴリズムは、コンテナ内の要素を検索、変更、並べ替え、統計情報の取得など、さまざまな目的で使用されます。 1. 非変更アルゴリズム これらのアルゴリズムは、コンテナ内の要素を変更せずに操作します。 1.1 find と find_if find(first, last, value): 指定した値 ...

学習の感想 振り返ると、この40日間の学習記録はかなり浅いものでした。実際に学習した時間は半分程度で、一部の時間ではオンラインコースのみを見てコードを書く練習をしなかった状況でした。40日間のうち、真剣に学習できたのは約15日間程度でした。来年の試験ではこのような学習方法は避けなければなりません。 今回の試験では時間配分を間違え、良い結果を得ることが ...

StringBuilder APIの基本操作 主要なStringBuilderメソッド append(String str)：文字列を末尾に追加します。 insert(int offset, String str)：指定位置に文字列を挿入します。 delete(int start, int end)：指定範囲の文字を削除します。 deleteCharAt(int index)：指定位置の文字を削除します。 reverse()：文字列を反転します。 toString()：StringBuilderをStringに ...