非再帰型Segment TreeのPythonによる実装 - Qiita
はじめに タイトルのとおり、この記事ではPythonによる非再帰型Segment Treeの実装を紹介したいと思います。 前提知識を「ほぼ」1 必要としないようにSegment Treeの説明から入るので、もう知ってるという方は読み飛ばしてください。→非再帰型Segment Treeの実装 Segment Treeとは 通称セグ木、セグメント木などと呼ばれているデータ構造で、長さ $N$ の配列{$a_i$}$_{i=0}^{N-1}$に対して、モノイド $(S,•)$ に関する次の2つの操作がどちらも時間計算量が $O(logN)$ で行えます。 $update(i, x)$: $a_i$ を $x$ に変更する $query(l, r)$: 半開区間 $[l,r)$ に対して $a_l•a_{l+1}•$…$•a_{r-1}$ を返す モノイドとして、一般的な足し算を考えると、$q
【図解】木のパスに関するクエリは HL 分解！ その仕組みと実装を図で理解する｜Heavy-Light Decomposition - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? この記事では木構造に関するアルゴリズム**「HL 分解 (Heavy-Light Decomposition，HLD とも)」について紹介します．このアルゴリズムを理解すると，様々な「木のパスに対するクエリ」**に対応できるようになります． HL 分解は少し難易度が高いですが，この記事では図を使って視覚的に理解できます．是非 HL 分解をものにしてください！ 1. HL 分解とは HL 分解では 根つき木 をバラバラに分解していきます (普通の木を根つき木にしながら HL 分解することもできます)． まずは分解後どうなるのか見てみましょ
接続辞書と日本語入力 - 増井俊之
増井俊之.icon はMacでもAndroidでもChromeOSでも自前の日本語入力システム(IME)を使ってるのだが、「接続辞書」を使う単純なアルゴリズムを利用している。 世の中で広く使われているモダンな日本語入力システムは高度な自然言語処理によってかな漢字変換を行なっているが、実は高度な自然言語処理を利用しなくても効率的に日本語入力することは可能である。たとえばSKKという日本語入力システムは単純な辞書とアルゴリズムしか使っていないにもかかわらず高速な日本語入力が可能だったりする。(SKKはもともとEmacs上での日本語入力用に開発されたもので、増井俊之.icon も結構使っていたのだが、キーボードの利用が前提でありモバイル機器では使いにくいとか日本語でしか使えないという制約がある) 接続辞書というのは「単語の次にどのような単語が続くか」を記述した辞書である。単語ごとに、読み/カテゴ
アルゴリズムロジック
問題へのリンク 問題概要座標 \((0,0)\) からスタートして \(N\) 回の移動で \((X,Y)\) に到達する確率を求めたい。 1回の移動では、上下左右それぞれの方向に確率 \(\frac{1}{4}\ ...
セグメント木を徹底解説！0から遅延評価やモノイドまで | アルゴリズムロジック
セグメント木とは セグメント木とは、完全二分木（全ての葉の深さが等しい木）によって実装された、区間を扱うのに適したデータ構造のことです。 区間に対する操作を対数時間 O(log n) で行えることが特徴で、競技プログラミングなどで頻出となっています。 セグメント木でできること セグメント木は、区間に対する操作やクエリを行うことができます。 特に、 区間上の値を更新する任意の区間上の最小値や合計値などを取得する などが対数時間でそれぞれ行えるのが強みです。 区間上の合計値などは、累積和などを使えば前処理 O(N) ・クエリ O(1) で取得することもできます。しかし、区間上の値の更新と、合計値の取得が入り乱れるような時は、セグメント木の方が有効になることが多いです。 以下では説明のために、区間上の最小値 Range Minimam Query(RMQ) を扱うセグメント木を例として説明します
Zip Files: History, Explanation and Implementation
Zip Files: History, Explanation and Implementation (26 February 2020) I have been curious about data compression and the Zip file format in particular for a long time. At some point I decided to address that by learning how it works and writing my own Zip program. The implementation turned into an exciting programming exercise; there is great pleasure to be had from creating a well oiled machine t
おしゃれなアルゴリズム
本スライドは某LT用に作成しました．厳密性より，非競プロerに向けて面白さを重視しています． 過去問題の解説です．
Implementing Raft: Part 0 - Introduction - Eli Bendersky's website
This is the first post in a multi-part series describing the Raft distributed consensus algorithm and its complete implementation in Go. Here is a complete list: Part 0: Introduction (this post) Part 1: Elections Part 2: Commands and log replication Part 3: Persistence and optimizations Part 4: Key/Value database Part 5: Exactly-once delivery Raft is a relatively new algorithm (2014), but it's alr
競プロのアルゴリズム関連略称まとめ - noshi91のメモ
随時募集しています 略称 正称 APSP All Pairs Shortest Path BB Branch and bound BBST Balanced Binary Search Tree BFS Breadth First Search BIT Binary Indexed Tree BM Berlekamp-Massey BM Boyer-Moore BSGS Baby-Step Giant-Step CHT Convex Hull Trick CRT Chinese Remainder Theorem D&C Divide and Conquer DAG Directed Acyclic Graph DEPQ Double-ended priority queue DFS Depth First Search DP Dynamic Programming DST Disjoin
高校生がアルゴリズムとスパコンの力で、京都の碁盤目状道路を13.9%効率化した話 - Qiita
2. 本研究で解く問題 「いざ研究しよう！」と思っても、条件や設定を決めないと何も始まりません。 まずは研究を分かりやすくするために、「一つの問題」に落とし込むことにしました。 問題設定 縦 $N$ 行・横 $N$ 列の大きさの碁盤の目があります。隣り合う交差点間の距離は 1 です。つまり、交差点が合計で $N^2$ 個あり、それぞれ座標 $(1, 1), (1, 2), ..., (1, N),$ $(2, 1), (2, 2), ..., (N, N-1), (N, N)$ に位置すると考えることもできます。 下の図は、$N = 4$ の場合の交差点の位置です。 あなたは、碁盤の目の交差点の位置は変えずに、道路の並びのみを変えることができます。上手く道路の並びを変えることで、できるだけ「便利」な道路網を建設してください。 「便利な道路網」って何？ 私は、以下の 2 つの条件を満たす道路
A paper algorithm notation
By Kragen Javier Sitaker, originally written 2014-08-26, last substantive update 2014-10-15, this paragraph added 2016-11-30. Pseudocode on paper is an important thinking tool for a lot of programmers, and on the whiteboard for programming teams. But our programming languages are very poorly suited for handwriting: they waste the spatial arrangement, ideographic symbols, text size variation, and l
GitHub - scandum/quadsort: Quadsort is a branchless stable adaptive mergesort faster than quicksort.
ロックフリーアルゴリズムによるFIFOバッファ - Qiita
はじめに 私が組み込みプログラミングを始めたころ(まだインターネットもなく組み込みマイコンもAKI-80とかZ80系主流で遊んでいた時代)に大学の先輩に教えてもらったテクニックです。今どきのCPU向けではないですが、私自身が古典的かつ重要な要素が含まれており、組み込みプログラミングに引き込まれたきっかけの一つでもありますので、当時を思い出しつつ記事にしてみます。 「ロックフリーなアルゴリズム」についてはこちらのWikipediaの記事がわかりやすいです。 これらのアルゴリズムは、割り込み禁止やミューテックスなどのロックを用いずに、割り込みハンドラやマルチタスク／マルチスレッドなどの異なる非同期な実行コンテキスト間で情報を渡すことを目的としており、今回はその応用内でのFIFOバッファの構成例となります。 近年ではArduinoなどの組み込みプログラミングも手軽に行える環境が増えています。また
グラフ描画アルゴリズムとNetworkxの裏側 - Qiita
0.グラフの描画ってどうやるの？ 二次元に描画するためには各頂点に適切に座標を与える必要がありますが、グラフは頂点と辺の情報しか持っていません。どのように頂点を配置すればよいのでしょう？？ この記事ではグラフをいい感じに配置するアルゴリズム Fruchterman-Reingold algorithm を説明します。Pythonだと networkxというライブラリで簡単に使用できます。しかし簡単すぎて悔しいので networkxの GitHub の実装を追いながら仕組みを確認していきます。 この記事の流れはこうです。 動かしてみる アルゴリズムの説明 Networkx の実装を追う 1.動かしてみる 動けば満足な方のために先に実装例を示しときます。Google colaboratory だと既にnetworkxがインストールされてるので、コピペですぐ試せます。 ランダムに配置 → ran
A new hash algorithm for Git
The Git source-code management system is famously built on the SHA‑1 hashing algorithm, which has become an increasingly weak foundation over the years. SHA‑1 is now considered to be broken and, despite the fact that it does not yet seem to be so broken that it could be used to compromise Git repositories, users are increasingly worried about its security. The good news is that work on moving Git
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Yoichi Iwata on Twitter: "群ラベル最短路の論文が更新されました。https://t.co/HTFB7f3fnD 縮約が不要になり計算量がO(nm)→O(m log n)に。 問題設定と手法(縮約版)の解説 https://t.co/5KXa3Vr2EL… https://t.co/KvKQ5FUADG"
アルゴリズムビジュアル大事典
[PDF]陣内佑 (2020) ヒューリスティック探索入門
もう数え上げも怖くない ~競プロ数え上げ問題35選~ - Qiita
SlowerLogLog – Evan Miller