Interpolation - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
多項式補間に関して教えてもらったのでまとめておきます。 何らかのN次関数P(x)があったとします。xが小さい場合は簡単に計算できる時、それを利用して大きなxに対しても求めたいです。 連立方程式を解くと各項の係数が求められますが、O(N^3)掛かってしまいます。 それをO(N^2)にする方法の１つとして、ラグランジュ補間があります。 Qi(x) = (x-0)*(x-1)*...*(x-N) / (x-i) という関数を考えると、N次多項式は必ず、 P(x) = c0*Q0(x) + c1*Q1(x) + ... + cN*QN(x) という形で書けるそうです。 この関数Qの嬉しい所は、xにiを代入すると、Qi以外は全部0になって除去できる所です。 xにiを代入して考えると、係数ciはP(i)/Qi(i)となっており、簡単に計算できます。 各Qを求めるためにO(N)で、項がN個なので、O(N
重み付きランダム抽出:Walker's Alias Method - Qiita
なにこの記事 重み付きランダム復元抽出アルゴリズムである、Walker's Alias Methodについて 重み付きランダム復元抽出 要素ごとに抽選される確率が異なり、(重み付き) 選んだ要素を都度母集団に戻す抽出方法(復元抽出) のこと。 素直に実装すると 重みをつけてランダムに何か出したいや 重み付きランダム のようになります。 線形探索で実装すれば、計算量は抽選1回毎にO(n) バイナリサーチなら準備にO(n)、抽選1回毎にO(log n) Walker's Alias Method 準備にO(n)で、抽選1回毎になんとO(1)というアルゴリズム。 同じ大きい集団に対して何度も抽選しないといけない用途向け。 (GAとか粒子フィルタとか。) ググればわかりやすい説明が出てきます。 図の上のような重みリストでは、 乱数が3~4の時にどの要素を抽出するかを最高で2回判定する必要があります
蟻本シリーズ 3 スライド最小値 - StatModeling Memorandum
今回は以下の問題を考えます。 長さNの数列x[1], x[2], ..., x[N]と数Kが与えられます。y[i] = min{x[i], x[i+1], ..., x[i+K-1]} (i = 1, ..., N-K+1)として定義される数列y[i]を計算しなさい。 この問題は両端キュー（デック, deque）を用いることで、なんとのオーダーで解けます。詳しくは蟻本の4-4節（p.300）を読んでください。 プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～ 作者:秋葉拓哉,岩田陽一,北川宜稔発売日: 2012/01/28メディア: 単行本（ソフトカバー） ここでは蟻本から例題を引用してN = 5, K = 3, x = {1, 3, 5, 4, 2}, y = {1, 3, 2}の場合について簡単に説明します。 まずd
蟻本シリーズ 2 ランダムウォーク - StatModeling Memorandum
今回は以下のランダムウォークの問題を考えます。 I×Jの大きさのグリッドがあります。(1,1)からスタートして、1ターンに上下左右4マスのうち移動できる方向にそれぞれ確率p1,p2,p3,p4で移動します。いくつかのマスには石が置いてあり、通行不可能になっています。(I,J)にはじめて辿り着くまでにかかるターン数の期待値を求めなさい。ただし、(1,1)から(I,J)に移動するパスが少なくとも1つは存在すると仮定します。 例：I = 3, J = 10 [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [1,] 1 0 1 1 1 0 1 1 1 0 [2,] 1 0 1 0 1 0 1 0 1 0 [3,] 1 1 1 0 1 1 1 0 1 1 0が石があるマスで、1が移動できるマスです。以降ではこのグリッドを「グリッドA」と呼びます。
蟻本シリーズ 1 ナップサック問題 - StatModeling Memorandum
「プログラミングコンテストチャレンジブック [第2版]」（通称：蟻本）という本がとてもよかったので、これから3回にわたって統計モデルを絡めた感謝の記事を書こうと思います。 プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～ 作者:秋葉拓哉,岩田陽一,北川宜稔発売日: 2012/01/28メディア: 単行本（ソフトカバー） 競技プログラミングはたまに実務で役に立たないとか言われていますが、僕はまったくそうは思いませんでした。プログラマーとしてもデータ解析者としても有益な考え方が満載で、ふと気づけば応用できる対象は至る所にあるように思いました。 今回は以下のナップサック問題と呼ばれる問題を考えます。 重さと価値がそれぞれWeight[i], Value[i]であるようなN個の品物があります。これらの品物から、重さの総和がMax
PHPのround関数とは一体なんだったのか - hnwの日記
（7/3 14:05追記）Javaに関する記述について誤認があったので盛大に書き換えました。Java 6、Java 7、Java 8それぞれで実装が変わっていたようです。 （7/13 23:55追記）本記事中ではroundを四捨五入と言い切ってしまっています。これは筆者がC99のroundを基準に考えているためですが、言語によっては偶数丸めになっているround関数も珍しくありません。ご注意ください。 PHPのround関数について、ネット上で次のような記述を見つけました。 PHP 四捨五入の計算を間違える唯一の言語として畏れられていましたが、そのバグは治っているかもしれません（治ってないかもしれません） 主要なプログラミング言語8種をぐったり解説 - 鍋あり谷あり 各言語を面白おかしく紹介する内容とはいえ、ずいぶん雑な理解だなーという印象です。ゆるふわな話だけでPHPがdisられ続けるの
Golangの新しいGCアルゴリズム Transaction Oriented Collector（TOC）
http://golang.org/s/gctoc Goの新しいGCのProposalが出た．まだProposal段階であり具体的な実装はないが簡単にどのようなものであるかをまとめておく． GoのGCはGo1.5において単純なStop The World（STW）からConcurrent Mark & Sweepへと変更され大きな改善があった（詳しくは“GolangのGCを追う”に書いた）．先の記事に書いたようにGo1.5におけるGCの改善は主にレイテンシ（最大停止時間）に重きが置かれいた．数値目標として10msが掲げられGo1.6においては大きなヒープサイズ（500GB）においてそれを達成していた． GCの評価項目はレイテンシのみではない．スループットやヒープの使用効率（断片化の対処）なども重要である．Go1.6までのGCではそれらについて大きく言及されていなかった（と思う）．例えばスル
高速ハッシュアルゴリズム – YOSBITS
この記事は特に高速なハッシュアルゴリズムをまとめた資料です。 暗号的な強度が重要でない場合に使用できるアルゴリズムと暗号強度が考慮されたアルゴリズムがありハッシュ関数の利用環境あわせて検討すべきである。また、実行速度は実行環境に依存するので実際の実行環境で実測して判断するべきである。 MurmurHash 2008年に”Austin Appleby”が考案した非暗号ハッシュアルゴリムです。このアルゴリズムは暗号化処理などに向いていない。MurmurHash3 は現在のバージョンで、32ビットまたは128ビットのハッシュを生成する。MurmurHash2 は古いバージョンで、32ビットまたは64ビットのハッシュを生成する。64ビットのハッシュ値生成するソースには2つの変種がある。64ビットプロセッサ用に最適化された用の MurmurHash64A と32ビットプロセッサ用に最適化された Mu
爆速ナンバーリンクソルバー（1）〜ナンバーリンクと充足可能性問題 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 先ほど、ブラウザで動くナンバーリンクソルバー（http://jkr2255.github.io/js_puzzle_solvers/numberlink.html）を公開しました。それについてまとめようと思ったのですが、1本の記事に書くには長すぎるので、少しずつ分けて書いていこうと考えています。 まずは、問題そのものである「ナンバーリンク」と、それの解法に使った「充足可能性問題」について解説します。 まず、「ナンバーリンク」って？ ナンバーリンクは、数独やクロスワードといった、（もともとは）紙と鉛筆で楽しむ「ペンシルパズル」の一種です。
2-SATと強連結成分分解 - naoya_t@hatenablog
ふと2-SATの事が気になって、復習がてらPractice RoomでSRM464のDiv1 Medium問題を開いてみた。（ちなみにSRM464には出場している） SAT (充足可能性問題, SATisfiability problem) についてはここの読者の皆さんはご存知とは思います。NP完全問題でおなじみのあれです (x_0 ∨ ¬x_1) ∧ (¬x_0 ∨ ¬x_3) ∧ ... みたいな論理式（乗法標準形）を満たす真偽値 x_0, x_1, ... の組み合わせが存在するか否か。（存在する場合、その組み合わせを知りたかったりする） 上の例ではすべての節が(高々)2変数なので2-SATと呼ばれる。 （2-SATは線形時間で解けるらしい）。 論理和 x ∨ y が論理包含 ¬x⇒y （または ¬y⇒x）に書き換え可能なことを利用して、論理式を有向グラフに変換してみたり 出来上がっ
アルゴリズムをビジュアル表示できコードでも確認できるサイト「Algorithm Visualizer」 - GIGAZINE
アルゴリズムをプログラムで表示した場合、アルゴリズムの概念自体が複雑な上に抽象的なコードのせいもあって、実行されるアルゴリズムのプログラムをイメージするのは難しいものです。そんな抽象的なアルゴリズムのプログラム学習には、コードだけでなく、実際にプログラムを走らせるときのログを表示しつつ、アルゴリズムをビジュアル化してくれる「Algorithm Visualizer」が非常に役に立ちます。 Algorithm Visualizer https://algorithm-visualizer.org/ Algorithm Visualizerは、バブルソートやバイナリーサーチ(二分探索)などのアルゴリズムを、プログラムとして表示させつつ、実際に実行した場合の動きを可視化したりログ化したりすることで、アルゴリズムの理解を深められるサービスです。 ページ左にアルゴリズム名がずらりと並んでおり、選択し
巡回セールスマンの計算量はO(n)というのはなんとなくわかるのですが動的計画法を使った時はO(n^2×2^n)というのが何故だ... - Yahoo!知恵袋
Ｏ（ｎ）で解けたら学術雑誌で大注目を浴びると思うのですが？ 動的計画法の肝は、同じ状態になるルートが多数あるとき一番いいルート以外切り捨てることです。 巡回セールスマン問題の状態は。 今まで通ってきた地点の組み合わせが２＾ｎで今いる地点がｎ通りなので。 動的計画法では ｎ*２＾ｎ通りの状態を考えこれらすべてから次の地点への移動を検証する必要があります。 これをｎ点回りおわるまで続けるのですが、この中で２＾ｎ通りでいらない状態を無視することで計算量をおとせます。 大雑把な計算量がｎ*ｎ*２＾ｎ となるわけです。
C++でブルームフィルタを実装する方法 | POSTD
ブルームフィルタとは、「ある要素が集合のメンバである可能性があるか、それとも確実に集合のメンバではないか」を効果的に確認することのできるデータ構造です。この記事では、C++でブルームフィルタを実装する簡単な方法をご紹介します。 ブルームフィルタとは何なのか 、また、 その背後にある多くの数学的要素 については紹介していませんので、ご了承ください。これらのトピックに関しては、素晴らしいリソースがあるので、そちらを参考にしてください。 インターフェイス まずは、ブルームフィルタを定義していきましょう。ここでは、3つのパブリック関数を定義していきます。 コンストラクタ ブルームフィルタにアイテムを追加する関数 アイテムがブルームフィルタにある可能性を確認するためのクエリを行う関数 また、フィルタの状態を保持するビットの配列を含んだ、メンバ変数についても定義します。 #include <vecto
点の集合を包含する球
IPSJ Magazine Vol.43 No.9 Sep. 2002 1009 点の集合を包含する球 ishihata@cs.meiji.ac.jp 3 (x1, y1), (x2, y2), (x3, y3) S = � � (y3y1)(x2x1)(y2y1)(x3x1) (y3y1)(x2x1) (y2y1)(x3x1) 3 1 2 3 (convex hull) 1 3 2001 11 H ■幾何の問題に関する一般論 1 1 2 20% 2 3 3 x-y 3 2 43 9 2002 9 1010 1 ■問題：点の集合を包含する球 3 n n 4 30 x-y-z x y z 0 100 0.01 5 0.00001 6 10 7 typedef struct { double x, y, z; } pos; int n; pos point[30]; p
g++拡張・tree - hogloidのブログ
g++拡張にpb_ds(policy based data structure)というのがあって、その中に便利なtreeというのがあります。 細かい使い方まとめみたいなページは見つかりませんでしたが、コンテストでの主な用法をまとめておきます。c++のsetの上位互換みたいな感じで使えます。 CF・TopCoderでは使えます。 用意: g++の新しそうなやつを使う #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #include<ext/pb_ds/tag_and_trait.hpp> using namespace __gnu_pbds; 宣言: tree<key,null_type,less<key>,rb_tree_tag,tree_order_statistics_node_up
やさしいハフ(Hough)変換講座 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 概要 ハフ(Hough)変換は、画像の中から直線や円などの図形を検出したい際によく用いられる手法の一つです。検出精度は高いですが、その分演算負荷が高く、またメモリも多く消費するなどの欠点があります。 しかし、理論が美しいことから、ぜひ覚えておきたい画像処理アルゴリズムの一つだと私は思いました。以下の記述は、次の記事を参考にしています。 Hough変換による画像からの直線や円の検出：CodeZine（コードジン） そもそもハフ変換って何を変換してるの？ 端的に言えば、座標系を変換しています。これだけでは何を言っているのかが分かりづらいと思
動的計画法入門（数え上げ） - ペケンペイのブログ
数え上げ系の DP について説明する。 この記事は DP 初心者を対象にしている。DP やるだけみたいなことを一度でも考えたことがある人は対象にしていない。 例題 次の問題を考えてみよう。 N 桁以下の 3 の倍数はいくつあるか。 N が小さければ全列挙できる。i 桁の数がすべて列挙できていれば、その後ろに 0～9 を付け足せば i+1 桁の数をすべて列挙できることを使う。 dp[i] := leading zero を含めて i 桁のすべての非負整数の集合 #include <iostream> #include <string> #include <vector> using namespace std; int modulo(string s, int mod) { int ret = 0; for (char c : s) ret = (ret * 10 + (c - '0'))
yukicoder No. 318 学学学学学 - pekempey's blog
(2015/12/12 2:04) 問題を勘違いしていたので一部修正しました。 問題文 http://yukicoder.me/problems/899 解法 ....t..t...t...のように1が複数個あったとしても、書き換えに影響するのは一番端にあるtだけ。そこで最初と最後を区間としてみることにする。そうするとb[i]の値はiを覆うtの最大値になる。 ある値xが最初に現れる位置がiならl[i]=x、最後に現れる位置がiならr[i]=x、それ以外のl[i]、r[i]はNILとしておけば、次のような処理でb[i]を決めていける。 for i in xrange(n): if l[i] != NIL: set.add(l[i]) b[i] = max(set) if r[i] != NIL: set.remove(r[i]) yukicoder No. 318 学学学学学 想定解 ちなみ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
計算量と僕とWeb開発 / computational complexity and I and Web
[AAAI-16] Tiebreaking Strategies for A* Search: How to Explore the Final Frontier