双対性2 自己紹介 東大情報科学科→情報理工(2016年3月博士卒) 国立情報学研究所助教 離散アルゴリズムの研究をしている 世界 1 位 (2010) 世界 2 位 (2011) 世界 3 位 (2009)3回優勝 (2013,2015,2016) 競プロ： wata Twitter: @wata_orz ICFPC
絶対にバグらない二分探索の実装パターンと、それがバグらない5つの理由 - Qiita
概要 絶対にバグらない二分探索の実装パターンと、それがバグらない5つの理由を紹介します。 めぐる式二分探索と比べると、コーナーケースに強いです（具体的には「解が存在する値」「解が存在しない値」の存在を前提しないので強いです）。 二分探索 二分探索とは、判定関数 $f(x): T \rightarrow bool\ (x \in [s, t))$ が広義単調増加であるときに、 $f(x) = true$ となる最小の$x$を$O(\log (t-s))$で求めるアルゴリズムです。 …が、二分探索は、$T = int$の時、必ずバグることで有名です。何をやってもバグります。 この記事では、以下のC++のコードが、任意の広義単調増加な$f$についてあらゆるコーナーケースに常に正しく動くことを納得させます。 お気持ち 初期値のngには、絶対に$f(x)$がfalseであるような$x$を入れておきた
df-pnアルゴリズムを用いた詰将棋Solverによる最善解・余詰の導出 - すぎゃーんメモ
以前書いた、詰将棋問題生成の続き。 memo.sugyan.com 逆算による詰将棋の問題生成の方法自体は悪くないとして (バグによって有り得ない局面が出来上がったりしてしまったりもしたけど)、正しく詰将棋問題として成立するものが出来上がっているかどうかを検証するためのSolverが必要不可欠であり、これのパフォーマンスが生成のパフォーマンスにも影響してくる、というようなことを書いた。 実際、前回の記事のときに実装したSolverでは 総当たり的に探索するのは3〜5手が限界 詰将棋のルールに則る動きに限定しても、有り得る局面は指数関数的に増加する 合駒が絡む問題に対して正しく解が導けないことがある 先の展開まで読まないと無駄な合駒かどうかの判定ができない といった問題があった。 df-pnアルゴリズムによる探索 2002年の論文「df-pn アルゴリズムの詰将棋を解くプログラムへの応用」が
UINT32正規化版高速sinは何をしてるのか - 落胆がらくた街
suzublog.hatenablog.com この記事でやってる、0~2PIをUINT32に正規化してやると高速でSinを計算できるという話。 ようやくこいつが何をしてるのか理解できたので忘れない内に書いとく。 元ソース。 float fastsin(UINT32 phase) { const float frf3 = -1.0f / 6.0f; const float frf5 = 1.0f / 120.0f; const float frf7 = -1.0f / 5040.0f; const float frf9 = 1.0f / 362880.0f; const float f0pi5 = 1.570796327f; float x, x2, asin; UINT32 tmp = 0x3f800000 | ( phase >> 7 ); if (phase & 0x40000000
"二分探索はX分探索において最強"の証明 - Qiita
0.背景 二分探索を初めて学習してから数年、今更二分探索を学習する機会があり、 「分割する個数を増やしても計算時間は二分探索より早くならないのか？」 という単純な疑問が浮かんだ。 サイズNの配列をx(>2)個の領域に分割すれば、計算時間はlogx N * １ループ当たりの比較回数となり、logx N < log2 Nなので、１ループ当たりの比較回数次第では早くならないか？と思ったからである。 しかしWebで検索してみたが、探索アルゴリズムの一環としてのX分探索に関する記事は(少なくとも日本語では)見つからなかった。 また「凸関数の極値を求める」という目的における三分探索や黄金比探索といった探索アルゴリズムがあることを知ったが、今回は二分探索と同様の目的における探索アルゴリズムを対象にするため、本稿では対象外とした。 参考 ・ 実数探索三種類解説 -nodchipの日記 ・ 三分探索と黄金分
実世界で超頻出！二部マッチング (輸送問題、ネットワークフロー問題）の解法を総整理！ - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 0. はじめに --- 二部マッチング問題は実世界で超頻出 はじめまして。NTTデータ数理システムでアルゴリズムを探求している大槻 (通称、けんちょん) です。 好きなアルゴリズムはタイトルにもある二部マッチングですが、会社ではなぜか「DP が好きな人」と呼ばれています。 以前に動的計画法 (DP) の典型パターンを整理した記事を執筆したのですが、DP と並んで超頻出の話題として二部マッチング問題があります。二部マッチング問題とは、例えばマッチングアプリなどに見られるように、2 つのカテゴリ間で最適なマッチングを構成していく問題です。実
一般的なダイクストラ法 - kirika_compのブログ
概要 ダイクストラ法を使うと、単一始点 s から全ての頂点への最短距離が計算できるのは有名だね。これを少し拡張することで、「s からの最短距離と、それを実現する最短経路の個数」の組を、全ての頂点について計算することができるわ。 詳しく 少し天下り的だけど、以下の半環を考える。 (a, x) + (b, y) := a < b ? (a, x) : a > b ? (b, y) : (a, x + y), (a, x) * (b, y) := (a + b, x * y) この半環を使って、[Mohri2002]の方法でダイクストラ法を行うことにより、s-vの最短距離とs-vの最短経路の個数が全ての頂点vについて分かる。 ソースコードは以下の通り。 gist.github.com ARC090 E - Avoiding Collision で確かめた。 https://beta.atcode
Earley Parsing Explained
Earley Parsing Explained Earley parsers are among the most general parsers out there. They can parse any context free language without restriction, and can even be extended towards context sensitivity. They are reasonably fast on most practical grammars, and are easy to implement (the core algorithms take less than 200 lines of code). On the other hand, most of the information I found about them i
My Favorite Algorithm: Linear Time Median Finding
Finding the median in a list seems like a trivial problem, but doing so in linear time turns out to be tricky. In this post I’m going to walk through one of my favorite algorithms, the median-of-medians approach to find the median of a list in deterministic linear time. Although proving that this algorithm runs in linear time is a bit tricky, this post is targeted at readers with only a basic leve
Advent Calendar 2017 : CPHBを少しだけ和訳してみた(前編) - kmjp's blog
この記事は、Competitive Programming Advent Calendar 2017 - Adventarの22日目の記事です。 「前編」とありますが、完成がいつになるのか、そして次回が中編なのか後編なのかは全く未定です。 (注・2018・2019のAdvent Calendarでも続編はありません。） ちなみに昨年分はこちらです。 Advent Calendar 2016 : ABC#001のA問題をコンパクトに解く - kmjp's blog はじめに すでに世の中には、日本語による競技プログラミングの解説書や教材が出ています。 著名なものには下記の物があります。*1 プログラミングコンテストチャレンジブック [第2版] | マイナビブックス (通称蟻本) 最強最速アルゴリズマー養成講座 | SBクリエイティブ (通称チーター本) プログラミングコンテスト攻略のためのア
Bing検索の裏側―BitFunnelのアルゴリズム - Hatena Developer Blog
はてなアプリケーションエンジニアの id:takuya-a です。 この記事では、Microsoft の検索エンジン Bing で採用された BitFunnel アルゴリズムを紹介します。 昨年のエンジニアアドベントカレンダーでは、文字列検索のアルゴリズム全般について紹介しました（文字列アルゴリズムの学びかた - Hatena Developer Blog）。今年はそのなかでも、インデックス（索引）を使った全文検索アルゴリズムについてのお話になります。 この記事の前半は全文検索の入門にもなっていますので、検索技術になじみがない方にも楽しんでいただけるのではないでしょうか。 逆に、「そんなのもう知ってるよ！」という方は、本題である「BitFunnel アルゴリズムの詳細」から目を通していただければと思います。 この記事は、はてなエンジニア Advent Calendar 2017の21日目の
線形時間RePair - 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 2017」14日目の記事です． はじめに 文字列を圧縮する日々が続いています． 今日は，文法圧縮アルゴリズムのひとつであるRePair1を，線形時間計算量で実現する方法を紹介したいと思います． 非常に高度な内容となった昨日に引き続き，今日もかなり難しい話を扱います．文法圧縮（とRePair）への入門が不十分だとはじき飛ばされるおそれがあるので，この分野になじみが薄いという方は，まず「文字列アルゴリズム Advent Calendar 2017」12日目の記事「文法圧縮入門
BDDとZDD -ブール関数と集合族の圧縮処理- - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 実質上位互換な記事を書いてしまったのでこちらをどうぞ「BDDとZDDを下から読んで再帰アルゴリズムを作る」 本記事は「文字列アルゴリズム Advent Calendar 2017」10日目の記事です．前後の記事は以下の通りです． 9日目: @okateim 氏による「最短超文字列問題」 11日目: @yoshikyoto 氏による「PHPでしりとりをして Code Quest の連鎖ノ試練をクリアする」です． えー、割と良くない体調の中で書いたので色々と多めにみていただきたく… あ，図も書いてないですね…手元にいい感じに図を描けるものが
文法圧縮入門 - 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 2017」12日目の記事です． はじめに 今日は文字列を圧縮してみます． P e t e r _ p i p e r _ p i c k e d _ a _ p e c k _ o f _ p i c k l e d _ p e p p e r s . _ A _ p e c k _ o f _ p i c k l e d _ p e p p e r s _ P e t e r _ P i p e r _ p i c k e d . _ I f _ P e t e r _
The Case for Learned Index Structures
Tim Kraska111Work done while author was affiliated with Google. MIT Cambridge, MA kraska@mit.edu Alex Beutel Google, Inc. Mountain View, CA alexbeutel@google.com Ed H. Chi Google, Inc. Mountain View, CA edchi@google.com Jeffrey Dean Google, Inc. Mountain View, CA jeff@google.com Neoklis Polyzotis Google, Inc. Mountain View, CA npolyzotis@google.com Abstract Indexes are models: a B-Tree-Index can b
Compact Directed Acyclic Word Graphを定義する - 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 2017」４日目の記事です． ３日目の記事は@itomomotiによる「周期性補題」でした． ５日目の記事は@kazu0x17による「木の同型性判定」です． 昨年の文字列アルゴリズム Advent Calendar では「Suffix Tree + Suffix Array = Suffix Tray」という記事を書きました． はじめに 文字列アルゴリズム，特に文字列に対する索引が好きです． 古典的な全文索引であるCompact Directed Acyclic Word Gr
JavaScriptで大量のオブジェクトの当たり判定を効率的にとる - Subterranean Flower Blog
ゲームなどのコンテンツにおいて、「当たり判定」から逃れることはできません。オブジェクトとオブジェクトが衝突したかどうかという判定は、インタラクティブコンテンツにおいて最も重要な部分になるからです。 当たり判定の実装自体は難しくありません。ですが、素朴な実装ですと、対象となるオブジェクトが大量である場合に、十分なパフォーマンスが出ません。これはオブジェクトの多い、現代的なゲームでしたり、弾幕シューティングなどを作るときに大きな障害となります。 この記事では、大量のオブジェクトの当たり判定を処理する、効率的な方法について紹介します。 まずは素朴に実装してみる 当たり判定の処理を語るには、ある程度ゲームの骨組みのようなものが必要になってきます。もちろんクラスなどを使わないベタ書きでもよいのですが、大変読みにくくなってしまいます。ですので、今回は、まず簡易的なゲームエンジンのようなものを作って、そ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Reddit - The heart of the internet
How fast can you bit-interleave 32-bit integers?
「数え上げテクニック集」を公開しました - DEGwerのブログ
