読者です 読者をやめる 読者になる 読者になる

セグメント木をあきらめた人のための平方分割

この記事はCompetitive Programming Advent Calendar 2016(その2)の12月15日の記事です。 www.adventar.org はじめに 基本事項 1点に対する変更クエリ・区間に対する質問クエリ Range Sum Query Range Minimum Query 区間に対する変更クエリ・1点に対する…

kd木のライブラリjtsiomb/kdtreeで最近傍探索を高速化してみた

次のような問題を解く必要がありました 3次元空間中に点群 と がある。ユークリッド距離が最小となるペア を報告せよ(決定的に振る舞うなら近似でもOK) もっと良い方法もあるのかもしれませんが,今回はKD木を使って くらいの計算量で解くことにします。調…

二分探索をバグらせないための考え方

問題設定 整数二分探索とは,以下の矢印の位置を求める問題である。 パターンA パターンB 解き方 前提として,範囲を閉区間で扱うと微妙にバグるので半開区間で扱う。while文の条件はどちらのパターンでも ub - lb > 1 である。 パターンA [lb, ub) として範…

SuffixArrayの説明に便利な単語を探す

SuffixArrayやその周辺領域での解説では、説明のための文字列としてabracadabraやmississippiといった単語が使われることが多いです。唐突ですが、別の単語を使ってみたくなったので、NLTKに付属のテキストから、使えそうな単語を探す指標をいくつか考えまし…

ウェーブレット行列とFM-indexで全文検索を書いてみた

www.youtube.com 去年のはじめに高速文字列本を買ったのですが、アルゴリズムを眺めるだけで実装はしていませんでした。特にウェーブレット行列は実装が大変そうにしか見えなくて敬遠していたのですが、ICPCの夏合宿で @hirokazu1020 さんに「あれはアイデア…

閉路の検出に負辺が入るとつらい

今回つまづいた問題はAOJでライブラリのverify向けの問題として公開されているAll Pairs Shortest Pathです。負の辺があり得る有向グラフ(|E| <= 9900, |V| <= 100, 多重辺や自己ループは無し)が与えられるので、負閉路が存在するなら"NEGATIVE CYCLE"を出力…

明治チョコレートパズルを解くプログラムを書いてみた

www.hanayamatoys.co.jp 問題 以下のブロックを6*11のグリッドにぴったり入るように置いてください。 答え コード ライセンスはMITです #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <limits> #include <iterator> using std::vector; using std::string; namespace { co</iterator></limits></vector></algorithm></iostream></cstring>…