半群の和が計算できる Deque - noshi91のメモ
概要 競プロでは知る人ぞ知るスライド最小値というテクニックは、より一般化されて sliding window aggregation という名前で知られています。本記事では両端で要素の追加/削除、全体での半群の和を得るというクエリを全て償却定数時間で処理するアルゴリズムの実装について説明します。 アルゴリズム 値と先頭からの累積和をペアにして要素として持つ stack を考えます。するとこの stack を2つ背中合わせにするように持てば、追加/削除は対応する stack に操作を行えばよく、累積和の更新も定数時間で実行可能です。また、総和を計算するクエリも左右の stack の累積和を単純に足せばよく、定数時間です。ここで問題となるのが、片方の stack から pop を多く呼び出すと空となり、それ以上 pop が出来なくなることにあります。ここで pop したいが対応する stack
量子アニーリングがチョットワカルようになる記事 - Yahoo! JAPAN Tech Blog
この例は規模が小さく、ちょっと頭で考えてれば答えがわかってしまうかもしれません。けれど、巨大なホテルだとしたら頭で考えるのが難しそうです。とにかくこの問題例をアニーリングマシンで解いてみることにします。 問題を量子アニーリングマシンで解くときは基本的に次のような流れに沿って解きます。 (1) 問題の抽出(2) 量子アニーリングマシン (イジングモデル) へのマッピング(3) アニーリングの実行(4) 解の解釈 (1) 問題の抽出 まずは、対象の問題を量子アニーリングで解くことのできるようにできる限りシンプルな問題に切り出すことが必要です。 この問題は実はグラフ頂点彩色問題に帰着させることができます。 グラフ頂点彩色問題とは、任意のグラフ G=(V,E) と色総数 K が与えられたとき、すべての頂点を、隣接する頂点 (すなわち、辺で接続されている頂点) が同色にならないという制約下でK色に塗
簡単なトライ - LINE ENGINEERING
これはLINE Advent Calendar 2018の14日目の記事です。 LINEの上村です。今日は文字列です。 はじめに トライ (trie)は文字列の集合を索引化し高速な検索を可能にするデータ構造であり、領域効率や高速性を向上させた多様なアルゴリズムが提案され種々の実装が公開されています。 IPアドレスの検索、形態素解析器における辞書からの候補の列挙、キー入力時のオートコンプリートといった有益な応用があり、文字列業界以外でもご存知の方は多いかもしれません。 この記事で紹介するsftrieは簡単で効率よい新たなトライ表現とそのC++実装です。 主な特徴は以下の通りです: 大きなアルファベットをサポートします。また、いわゆるNULL文字も必要としないため、バイト列やASCIIコードからUnicode、単語等に割り振ったIDのような一般の整数まで、様々な値を文字型として扱えます ノード
Big Sky :: flatten() に再帰は必要ない
先日、mopp さんが Vim に flatten() を追加するプルリクエストを追加してくれたのだけど、その時の記憶を整理する為に書く自分の為の記事。 add flatten() to flatten list by mopp - Pull Request #3676 - vim/vim - GitHub I'm a bit confused by the maxdepth argument. I would expect it to specify the maximum depth of the r... https://github.com/vim/vim/pull/3676 Vim script のリストは以下の様に、異なる型が混在できる。Ruby や他のスクリプト言語でも一般的。そしてスクリプト言語には一般的にリストを平坦化する為の flatten という関数ないしはメソッドが
The Swiss Army Knife of Hashmaps | Arrow of Code
A while back, there was a discussion comparing the performance of using the hashbrown crate (based on Google’s SwissTable implementation1) in the Rust compiler. In the last RustFest, Amanieu was experimenting on integrating his crate into stdlib, which turned out to have some really promising results. As a result, it’s being planned to move the crate into stdlib. While the integration is still ong
最短包含区間問題 - Qiita
本記事は、「データ構造とアルゴリズム Advent Calendar 2018」 11日目の記事です。 10日目の記事は @Gaccho 氏による「完全ローグライクダンジョン生成アルゴリズム🚪」でした。 12日目の記事は @Gaccho 氏による「「アルゴリズムこうしん」のアルゴリズムを作成する」です。 本記事では、「最短包含区間問題」という問題についてお話します。 本記事には新しい概念や高度なテクニックは登場しないため、アルゴリズムを生業とされている皆様にはお楽しみいただけないかもしれませんが、どうぞ最後までお付き合いください。 問題定義 以下のような、区間集合に対する問題を考えます。なお特に断りがない限り、本記事に登場する数値はすべて正の整数値であるとします。 最短包含区間問題 事前入力： $[1 ..N]$上の、互いに包含関係のない（ネストしない）区間の集合 $I$ クエリ入力：
Implicit Treap - 競プロ練習記録
この記事はCompetitive Programming (1) Advent Calendar 7日目の記事とISer Advent Calendar 8日目の記事として書かれました。 TL;DR Implicit Treapを実装しました。以下の操作がクエリ毎O(logn)で可能です。 配列のランダムアクセス 配列の任意箇所へのinsert 任意要素のerase 任意区間に対するsum, max, min等のクエリ 任意区間に対する加算、更新等のクエリ 任意区間のreverse 任意区間のrotate Implicit Treap上の二分探索 この記事では一般的なTreapから順を追って説明していこうと思うのでImplicit Treapだけコピペして使いたい！という人は最後の方へどうぞ。 追記 bug fixとかをした最新の実装はここにあります。 [12/24] [] operato
定数時間MSBアルゴリズム - Qiita
1-4ビット目yyyyはxxの値によって変わりますが、フラグの値は$X$のMSBと$A$中の１の位置で決まります。$A$の１が$X$のMSBより左にあるとフラグは０、さもなければフラグは１です。よって$X$に対してこの引き算を全部試せば、MSBの数だけ１が立ったフラグが手に入ることになります。 これを利用して$X’$を作っているのが下の図です。$X$にフラグをつけて√w個コピーしたあと、フラグで区切られた各区間（ブロック）に対して上記の引き算を一度に実行し、その後yyyyの部分をビットマスクで0クリアしたのが$X'$となります。$X'$のビット長は$\sqrt{w}(\sqrt{w}+1)=w+\sqrt{w}$なので、２ワード上で演算すれば$X'$は定数時間で計算できるというわけです。 X'の１を定数時間で数える方法について １が立っているビットを定数時間で数えるのは結構難しいのですが、
ハミング距離と鳩ノ巣原理 - Qiita
見ての通り地獄です。$k = 30$ で六百五十二京九千九百六十九兆八千九百三億千七百九十三万（ろっぴゃくごじゅうにけいきゅうせんきゅうひゃくろくじゅうきゅうちょうはっせんきゅうひゃくさんおくせんななひゃくきゅうじゅうさんまん）になります。3 4 そもそも、線形探索より高速に検索することが目的でしたので、$Q$ のサイズがデータの個数 $n$ を上回っては元も子もないのです。例えば $n$ が10億でも、$k = 8$ で $Q$ のサイズは $n$ をあっけなく上回ります。 でもまぁ安心してください。「だから皆さん線形探索を使いましょう！」なんてオチではないですし、まだ鳩も出てきてないです。以下では、この転置インデックスを用いた解法を上手く活用し、高速に問題を解くマルチインデックスという手法を紹介します。 マルチインデックス ここからは、転置インデックスによる解法を大きいパラメータに対し
01-BFSのちょっと丁寧な解説 - ARMERIA
先日Twitterで少し話題になったので書いてみます。データ構造とアルゴリズム Advent Calendar 2018 の8日目の記事でもあります。 「01-BFS」というものをちょっと丁寧に解説します。これは以下のような問題を解くことができるアルゴリズムです。 辺の長さが0または1である有向グラフにおいて、ある1つの始点から全頂点への最短路の長さを効率的な計算時間で求めよ。 ※図のグラフは非循環（DAG）ですが、必ずしもDAGである必要はないです。 この記事では01-BFSの解説の前に「ダイクストラ法」「幅優先探索」をそれぞれ復習し、その流れで01-BFSを解説します。必須ではありませんが、これら2つのコードを書いたことがない人は是非そちらからやってみてください。 ダイクストラ法 多くの人は 深さ/幅優先探索→ダイクストラ法 の順に学ぶと思いますが、今回は逆の記載順にしています。 ダイ
ワンス・アポン・アン・アルゴリズム - 共立出版
本書は、「計算」にまつわる様々な概念を、日常生活やよく知られた物語にたとえて描いている。『ヘンゼルとグレーテル』は森を抜けて家に帰るためのアルゴリズムを実行しており、『恋はデジャ・ブ』は決定不可能な問題の話であり、『シャーロック・ホームズ』はデータ構造を駆使して事件を解決している。『ハリー・ポッター』の世界の魔法は型と抽象化を通して理解でき、『インディ・ジョーンズ』は探索の複雑さを体現していることになる。議論されている内容は、アルゴリズム、記号と表現、データ構造、P=NP問題、言語・構文・曖昧さ、制御構造とループ、再帰、停止性問題、型、アルゴリズムの検証など多岐にわたる。 ・森に置き去りにされた『ヘンゼルとグレーテル』は、どうやって家に帰った？ ・『シャーロック・ホームズ』は犯人を見つけるのにどんなデータ構造を使った？ ・『インディ・ジョーンズ』が潜り抜けた死の罠はどれくらい難しい問題か？
ハルヒ問題（最小超置換問題）の紹介 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? はじめに 皆さんこんにちは、「データ構造とアルゴリズムAdvent Calendar」の作成者、文字列大好き文字列初心者の@kgotoです。 一昨年と去年は「文字列アルゴリズムAdvent Calendar」を作り、去年は念願の完走をしました。有り難いことに反響も大きかったです！ 今年は「データ構造とアルゴリズム」と対象を広げて、一瞬でカレンダーの枠が埋まるのでは！？とドキドキしていたのですが、蓋を開けてみるとなんとまだ11日も空きがあります！！ ちょっと寂しいですね。。。 もちろん無理に参加してくれとは言いませんが、この記事を読んでち
競プロとかに使うアルゴリズム実装メモ（二分探索、2次元累積和、しゃくとり法） - 甲斐性のない男が機械学習とか最適化とかを綴るブログ
はじめに アルゴリズムメモ第３段です。今回は二分探索法、２次元累積和、しゃくとり法と様々な問題に使える汎用的なアルゴリズムを書いていきます。 今回は勉強のため、アルゴリズムの本質的な部分を記述した抽象クラスと実際の問題を解く具象クラス（関数オブジェクト）を分け、テンプレートメソッドパターンもしくはストラテジパターンを用いてコーディングしました。 二分探索 用途 広義単調増加関数または広義単調減少関数が条件を満たし、かつ、条件成立と不成立の境界となる点を探索（条件成立と不成立の境界が１つのみ） ソート済み配列から条件が成立する値が存在するかの判定 アルゴリズムのポイント 変数を探索範囲の最小値、変数を最大値で初期化 をの中点（例えば、で求める）として、が条件を満たすか否かを判定 このとき、見つけたい点（条件成立と不成立の境界）がより小さいか、大きいかはが広義単調増加（減少）関数なのでわかる
意外と解説がない！動的計画法で得た最適解を「復元」する一般的な方法 - Qiita
NTTデータ数理システムでアルゴリズムを探求している大槻 (通称、けんちょん) です。 好きなアルゴリズムは最小カットやマッチングですが、会社ではなぜか「動的計画法が好きな人」と呼ばれています。今回は動的計画法を用いて得られた最適解を復元するための汎用的な方法について紹介します。 0. はじめに 動的計画法を用いて効率的に解くことのできる最適化問題は数多くあります。パッと思いつくだけでも ナップサック問題 迷路などの最短路問題 区間スケジューリング問題 音声認識パターンマッチング問題 レーベンシュタイン距離 発電計画問題 分かち書き 隠れマルコフモデル ... などなど、多種多様な分野の問題を動的計画法によって効率よく解くことができます。このように、分野横断的な活用をできることが、動的計画法をはじめとした数理工学的手法の特長であり醍醐味であると常々感じています。今回は動的計画法によって得ら
Ask HN: What's your favorite “elegant”/“beautiful” algorithm? | Hacker News
I always push my devs to really study the Bittorrent protocol. The elements of the protocol are all fairly easy to understand, but it's gorgeous to see how elegantly it solved a social problem rather than a computational problem. The tit-for-tat and fast-finish protocols are incredibly graceful ways to create virtuous cycles in a social/technical hybrid, and replaced very real vicious cycles in pr
Meow Hash
This is a temporary landing page for Meow Hash. I have a number of updates I need to post, and haven’t had time. At the moment, Meow Hash is the fastest bulk hash that passes quality testing, as you can see from the smhasher3 suite results: There is still a lot of work that could be done on Meow Hash, but, it is one of those things that only gets updated when time permits.
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Billion-scale similarity search with GPUs - Speaker Deck
Pickler combinators (part 1) - Papers We Love / FP Essentials - YouTube
Aho-Corasick
[1806.06726] Zip Trees