中学生にもわかるウェーブレット行列 - アスペ日記
id:echizen_tm さんの記事「ウェーブレット木の効率的で簡単な実装 "The Wavelet Matrix"」から始まったウェーブレット行列ブームから半年以上が過ぎ、すでに枯れた技術として確立されつつある感があります。 …嘘です。 日本以外ではあんまり来ていません。 理由としては、やはりアルファベット圏では単語境界が明確であるため、こちらの記事で書かれているような「キーワード分割の難易度」といったことがあまり問題にならないということがあるかもしれません。 まあ、そういうわけで局所的に来ているウェーブレット行列ですが、日本語をはじめとする単語境界のない言語圏にとっては重要なネタであると思うため、解説記事を書き直して*1みようと思います。 ウェーブレット行列でできること 主となる操作は、文字列に対する 定数時間の rank() と select()*2 です。 rank() は、「文
A/Bテストよりすごい？バンディットアルゴリズムとは一体何者か - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? オバマ大統領の再選に大きく寄与したことで大きな注目を集めているA/Bテスト。A/Bテストを導入した、することを検討している、という開発現場も多いのではないだろうか。 そんな中、Web上で次のような議論を見つけた。 20 lines of code that will beat A/B testing every time Why multi-armed bandit algorithm is not “better” than A/B testing 一言でまとめると「A/Bテストよりバンディットアルゴリズムの方がすごいよ」「いやいやA
様々な全域木問題
最小カットを使って「燃やす埋める問題」を解く方法について、問題とソースコードつきで、まとめました。ニコニコ生放送「TopCoderでプログラムしてみた」2000回記念放送の資料です。
iTunes11のアルバム情報表示に使われるオシャレアルゴリズムを考える | fladdict
iTunes11がリリースされましたね。賛否両論を呼びそうな大変更。 このiTunes11、アルバム選択時の情報画面がもの凄く凝ってる。なんとアルバムジャケットにあわせて情報の色が変化するんよ！！ 何これオシャレ！ どういうアルゴリズムになっているのか、とっても気になる。 仮定としては、 ジャケットを16〜32色程度で減色、パレット抽出する。 四辺のエッジに含まれる色から、最多ピクセル色を背景に採用。 残りの色の中で、背景色と一定距離（RGB or 色相）がある最多ピクセル色を文字色1として採用。 残りの色の中で、背景色と一定距離（RGB or 色相）がある最多ピクセル色を文字色2として採用。 どうしても適切な色がない場合、白か黒を文字色に採用。 アルバムの四隅に対し、背景色でインナーシャドーをかける という感じかなと。多分これであってる。 アルゴリズムで文脈にあった綺麗な配色を作るってい
おねえさんのコンピュータを作ってみた
まだやってたのか、と言われてしまいそうですが、おねえさんが計算にかけた時間と比べればまだまだです。 『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！ この動画で出てくるおねえさんのコンピュータを作ってみた、というお話。 おねえさんのコンピュータからアクセスできます。 検索アルゴリズム HTML+CSSでコンピュータの画面を再現してみました。Javascriptを組むより、そっちの方に時間がかかった気がする。 経路の描画にはCanvasを使ってます。 この問題は自己回避歩行(Self-avoiding walk)と呼ばれるものらしいです。 単にグラフ上を移動するだけなので、小さいなサイズなら単純な深さ優先検索(DFS)で解けます(大きなサイズで何が起こるのか・・・それは動画で)。 実装では、DFSによる検索プログラムをWeb Workerを使って走らせ、スタートとゴールを
プログラミングコンテストでの乱択アルゴリズム
2013/1/9に統数研チャンネルにて、ウェーブレット木の解説をしました。岩波書店より出版されました「高速文字列解析の世界」の解説になっています。
プログラマが解くのに1時間かかる問題を機械学習に放り込む話 | ぱろすけのメモ帳
プログラマが解くのに1時間かかる問題を機械学習に放り込む話 By ぱろすけ on 4月 11th, 2012 皆様、 Twitter やら facebook で数カ月前に爆発的に拡散された以下の問題をご存知でしょうか。 ご存知の方が多いでしょうね。単に、イコールの左側の4つの数字の丸の数の合計がイコールの右側に等しい、それだけですね。とても簡単な問題です。ちなみに僕は解けませんでした。 これについて、昨日このようなエントリが投稿され、話題になっています。 プログラマが解くのに1時間かかるという問題が普通にプログラマな方法で5分で解ける話 http://d.hatena.ne.jp/nowokay/20120410 こりゃあ炎上するでしょうねえ。だって、プログラマも何も関係なく、ふつうに問題を解いているのですから。 先ほどのエントリでは、イコールの左側の数値は変数であり、それを足しあわ
素数列挙について - MugiCha
Competitive Programming Advent Calendar 3日目は、数学っぽい話をしたいと思います。 N以下の素数をすべて求めよ。 N以下の素数の個数を求めよ。 A以上B以下の素数の個数を求めよ。 こんな感じの問題を見たことがあると思います。また問題としてでなくても、解く過程にこのようなサブ問題を解かなければいけない場合もよくあると思います。素数については説明しなくてもいいですよね？ このような問題を素数列挙と呼ぶことにします。素数列挙ができれば、大きい数の素数判定や素因数分解をめっちゃ高速化したり、トーティエント関数、メビウス関数等、数学系のいろんな関数を求めたりできます。最近のもので素数列挙がほぼ必須のものだと Codeforces Beta Round #86 (Div. 1 Only) C. Double Happiness ICPC 国内予選 2011 A
Soft maximum 関数
Soft maximum 関数というものがある。簡単に言えば「なだらかな max 関数」だ。下のグラフのような曲線を描く（角張っているのが普通の max 関数）。 式も簡単だ。次のようなシンプルな式で表される。 softmax(x, y) = log(exp(x) + exp(y)) これをちょっといじくって次のようにすれば “soft minimum” 関数も実現できる。 softmin(x, y) = -log(exp(-x) + exp(-y)) 更にこのふたつを組み合わせれば “soft clamp” 関数も可能だ。 softclamp(x, min, max) = log(exp(max) + exp(-log(exp(-min) + exp(-x)))) ゲームなどを作っていると、とにかく値の変化をなだらかにしたいという場面がよくある。イーズイン・アウトと比較すると使用の機会は
Blogopolisから学ぶ計算幾何 記事一覧 | gihyo.jp
運営元のロゴ Copyright © 2007-2025 All Rights Reserved by Gijutsu-Hyoron Co., Ltd. ページ内容の全部あるいは一部を無断で利用することを禁止します。個別にライセンスが設定されている記事等はそのライセンスに従います。
アルゴリズムの勉強のしかた - きしだのHatena
この記事で、アルゴリズムの勉強はアルゴリズムカタログを覚えることじゃないよということを書きました。 プログラムの理論とはなにか アルゴリズムの勉強というのは、スポーツで言えば腕立て伏せや走り込みみたいな基礎体力を養うようなもので、「ソートなんか実際に自分で書くことないだろう」とかいうのは「サッカーは腕つかわないのに腕立ていらないだろう」とか「野球で1kmも走ることなんかないのに長距離の走り込みいらないだろう」とか言うようなものです。 Twitterでアルゴリズムの勉強とはなにかと尋ねられて、「アルゴリズムの基本的なパターンを知って、それらの性質の分析のしかたをしって、いろいろなアルゴリズムでどのように応用されているか知って、自分が組むアルゴリズムの性質を判断できるようになることだと思います。 」と答えたのですが、じゃあ実際どういう本で勉強すればいいか、ぼくの知ってる本からまとめてみました。
常識を覆すソートアルゴリズム！その名も"sleep sort"！ - Islands in the byte stream (legacy)
TwitterのTLで知ったのだが、少し前に海外の掲示板で"sleep sort"というソートアルゴリズムが発明され、公開されたようだ。このアルゴリズムが面白かったので紹介してみる。 Genius sorting algorithm: Sleep sort 1 Name: Anonymous : 2011-01-20 12:22 諸君！オレは天才かもしれない。このソートアルゴリズムをみてくれ。こいつをどう思う？ #!/bin/bash function f() { sleep "$1" echo "$1" } while [ -n "$1" ] do f "$1" & shift done wait example usage: ./sleepsort.bash 5 3 6 3 6 3 1 4 7 2 Name: Anonymous : 2011-01-20 12:27 >>1 なん…だと
Welcome to Herbert Online Judge
Adobe Flash has ended its life. While I don't have plan to translate the player to HTML5, you can continue to play HOJ using HOJ Supporter developed by pasta-san. 1844 problems available. 1428 registered users. 85111 solutions have been submitted. Recent Submissions 2025-07-04 17:39:52 : kimukimu cleared problem 0014 in 8 bytes. 2025-04-26 05:25:01 : lucjansz cleared problem 0004 in 20 bytes. 2025
経路探索アルゴリズムの「ダイクストラ法」と「A*」をビジュアライズしてみた - てっく煮ブログ
as詳解 ActionScript 3.0アニメーション ―衝突判定・AI・3DからピクセルシェーダまでFlash上級テクニック を読んでいて、経路探索のアルゴリズムで A* が取り上げられていました。A* については、いろいろ検索して調べたりもしたのですが、やっぱり本に書いてあると理解しやすいですね。せっかくなので自分流に実装してビジュアライズしてみました。ダイクストラ法まずは A* の特別なケースでもあるダイクストラ法から見ていきます。クリックすると探索のシミュレーションが開始します。スタート地点(S)からゴール(G)への探索が始まります。色がついたところが「最短経路が決定した場所」です。スタート地点から少しずつ探索が完了していきます。半分ぐらい完了しました。まだまだ進みます。最後まで終わりました。最短経路を黒色矢印で表示しています。ダイクストラ法は、スタート地点から近いノード(=マス
DHTのアルゴリズム - WebLab.ota
分散ハッシュテーブル - Wikipedia DHTは、ピュアP2Pであってもネットワーク負荷はそれほど上がらず、ネットワーク上のコンテンツを漏れなくかつ高速に探索することを可能にする。従来のピュアP2Pで採用されていた通信では、数10万ピアぐらいが限界だとされているが、DHTを使うと数10億ピアを探索範囲とすることが可能となる。しかし、実装がむずかしいことが欠点となる。 DHTの欠点は、一般的に完全一致探索しか行えないことである。特に正規表現のような複雑な検索をDHTのみで実現することは不可能である。 代表的なDHTのアルゴリズムを説明している日本語文献を探してみた． Chord この節では，DHT の代表的なアルゴリズムであるChord について説明する．Chordのハッシュ空間上での距離の定義は，ハッシュ値の差の絶対値である．図3.5のように，データ保有ノード (図中の青点) を，そ
アルゴリズムの紹介
ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。 元々は、自分の頭の中を整理することを目的にこのコーナーを開設してみたのですが、最近は継続させることを目的に新しいネタを探すようになってきました。まだまだ面白いテーマがいろいろと残っているので、気力の続く限りは更新していきたいと思います。 今までに紹介したテーマに関しても、新しい内容や変更したい箇所などがたくさんあるため、新規テーマと同時進行で修正作業も行なっています。 アルゴリズムのコーナーで紹介してきたサンプル・プログラムをいくつか公開しています。「ライン・ルーチン」「円弧描画」「ペイント・ルーチン」「グラフィック・パターンの処理」「多角形の塗りつぶし」を一つにまとめた GraphicLibrary と、「確率・統計」より「一般化線形モデル」までを一つにまとめた Statistics を現在は用意して
最強最速アルゴリズマー養成講座：あなたの論理的思考とコーディング力は3倍高められる (1/2) - ITmedia エンタープライズ
全世界で20万人を超える凄腕のコーダーが集うプログラミングコンテスト「TopCoder」。本稿では、アルゴリズム部門のSRMで取り上げられる問題を考えながら、論理的思考力およびコーディングのテクニックを養っていきます。 はじめに はじめまして。高橋直大です。本連載「最強最速アルゴリズマー養成講座」では、全世界で20万人を超える凄腕のコーダーが集うプログラミングコンテスト「TopCoder」について、そこで出題される数学・アルゴリズムのパズルを考えることで、コーディングのテクニックおよび論理的思考力を磨くことを目的に開始するものです。ここで扱う技法は主にアルゴリズムのそれですが、その根底にはロジカルな思考術が存在します。そうした能力を養いたい方にとって少しでも役に立てれば幸いです。 なお、本稿は必要に応じてコーディング例も紹介しますが、TopCoderで出題される問題の中から比較的やさしい問
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Evolutionary systems & genetic algorithms - GenerativeArt
Main Page - GenerativeArt
liris.org
