問題 I : 乱択平衡二分探索木
東京大学プログラミングコンテスト 2011 問題 L : 𝐿 番目の数字 東京大学大学院情報理工学系研究科 秋葉 拓哉 2011/05/14 東京大学駒場キャンパス 問題概要 • 各ノードに数字が決まってるツリーがある • 以下のタイプのクエリを大量に処理: ある頂点 𝒗 から 𝒘 への経路上の数字で， 𝒍 番目に小さい物を求めよ 頂点番号 頂点 1 に決ま っている数字 例: 頂点 1 から頂点 6 への経路での，3 番目 → 2, 5, 8, 7 の 3 番目 → 7 が答え 問題を変形 • 頂点 1 を根にして，向き付きの木にする • 以下を効率的に計算できるか？ 頂点 𝒗 から根までで 𝒙 以下が何個あるか？ 例: 頂点 4 から根に 6 以下は何個あるか？ → 8, 5, 2 に 6 以下は何個あるか？ → 2 個 それができると？ • それができると，任意の 2 頂
明日使えないすごいビット演算
最適輸送問題（Wasserstein 距離）を解く方法についてのさまざまなアプローチ・アルゴリズムを紹介します。 線形計画を使った定式化の基礎からはじめて、以下の五つのアルゴリズムを紹介します。 1. ネットワークシンプレックス法 2. ハンガリアン法 3. Sinkhorn アルゴリズム 4. ニューラルネットワークによる推定 5. スライス法 このスライドは第三回 0x-seminar https://sites.google.com/view/uda-0x-seminar/home/0x03 で使用したものです。自己完結するよう心がけたのでセミナーに参加していない人にも役立つスライドになっています。 『最適輸送の理論とアルゴリズム』好評発売中！ https://www.amazon.co.jp/dp/4065305144 Speakerdeck にもアップロードしました: https
流行のIT技術を追うのをやめたらプログラマとして成長した話
私はもともと普通のプログラマとしてキャリアをスタートしましたが、2007年くらいから脱プログラマを目指してソフトウェア起業家として経営に軸足を移してきました。 それから8年くらいが経過して思うのは、経営者として大きな成功をおさめる前に、自分のプログラマとしての実力がめきめきとアップしてしまったということです。 8年前の私は、プログラマとしては基礎力はあるものの全般的には未熟であったように思います。コードも荒削りで、とにかくかろうじて動くものを作ることに四苦八苦していました。が、いまはプログラマとしてずっと良い仕事ができています。 この8年間は、自分でコードも書いていたので、経験が増えたことによって、良いコードを書けるようになったという面も多々あるとは思います。しかし、そのあいだ技術書を読むことはすっかりやめてしまい、流行の技術などは完全無視してきました。 経営層の一員として働くので、プロジ
Amortized analysis - Wikipedia
In computer science, amortized analysis is a method for analyzing a given algorithm's complexity, or how much of a resource, especially time or memory, it takes to execute. The motivation for amortized analysis is that looking at the worst-case run time can be too pessimistic. Instead, amortized analysis averages the running times of operations in a sequence over that sequence.[1]: 306 As a conclu
【アルゴリズム】Project Euler Problem 15 解答:動的計画法を用いて40C20の値を求めてみた - データマイニングと数学の備忘録
2015-06-13 【アルゴリズム】Project Euler Problem 15 解答:動的計画法を用いて40C20の値を求めてみた C C言語 ProjectEuler 数学の問題をプログラムを使って解くサイト「Project Euler」。今回はその問題15とその解説をしたい。数学やProject Eulerやアルゴリズムに興味のある方は是非読んで欲しい。Problem 15Lattice paths Problem 15Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down,there are exactly 6 routes to the bottom right corner. How many such routes are ther
深さ優先探索による塗りつぶし
2. 深さ優先探索とは 探索とは • 探索とは，可能性を調べながら，解を探す方法です 深さ優先探索とは • 最も基礎的な探索の方法です 本スライドで学ぶこと • 深さ優先探索による「塗りつぶし」 • 深さ優先探索の再帰関数による実装 • 深さ優先探索のスタックによる実装 2015/6/6 2
最短経路を見つけるアルゴリズムをビジュアルで見る「PathFinding.js」
カーナビやスマートフォンのマップアプリなど、目的地への最短ルートを一瞬で割り出してくれるサービスのお世話になっている人も多いと思いますが、その仕組みがどうなっているのかを知っている人はほとんどいないはず。その処理には、ルート探索専用のアルゴリズムが用いられているのですが、そんなアルゴリズムの動作する様子や、種類の違いによる結果の変化をわかりやすく見せてくれるサイトが「PathFinding.js」です。 PathFinding.js http://qiao.github.io/PathFinding.js/visual/ このサイトでは、スタート地点からゴール地点までの最短ルートを発見するさまざまなアルゴリズムを、自分で設定を変えながらインタラクティブに体験できるようになっています。2点の間に障害物を配置することも可能で、以下のムービーでは画面左下の緑色の地点から右上にある赤い地点までのル
Wikispaces
We are sorry, but the site you are looking for no longer exists Wikispaces was founded in 2005 and has since been used by educators, companies and individuals across the globe. Unfortunately, the time has come where we have had to make the difficult business decision to end the Wikispaces service. We first announced the site closure in January 2018, through a site-wide banner that appeared to all
AlphaBeta探索で経路依存の値を判定する方法 - Qiita
なんぞ？ AlphaBeta探索では、ゲーム木を木構造とみなして探索しているけど、現実的には合流があったりするので、それを効率的に処理するため(だけではないけど)に置換表があったりして、しかしゲームによっては辿った経路によって発動したりしなかったりするルールがあったりなんかもして、色々めんどくさいわけです。 そんなわけで、AlphaBeta探索をしていて、その時の評価値が経路に依存したものなのか否かを判定したくなったりすることもあるわけですが、割と頭がこんがらかるので、実装方法をまとめてみました。 どうやるの？ ↓こんな感じ。 末端では、それが経路依存な性質を持つか否かでフラグを設定する。 αを超えた場合(βカットを含む)は、αを超えた子ノードがtrueなときだけtrueにする。 αを超えなかった場合は、子ノードがどれか一つでもtrueならtrueにする。 β以上の子ノードがあった場合、そ
adilet.org - adilet リソースおよび情報
This webpage was generated by the domain owner using Sedo Domain Parking. Disclaimer: Sedo maintains no relationship with third party advertisers. Reference to any specific service or trade mark is not controlled by Sedo nor does it constitute or imply its association, endorsement or recommendation.
Algorithms for calculating variance - Wikipedia
Algorithms for calculating variance play a major role in computational statistics. A key difficulty in the design of good algorithms for this problem is that formulas for the variance may involve sums of squares, which can lead to numerical instability as well as to arithmetic overflow when dealing with large values. A formula for calculating the variance of an entire population of size N is: Usin
Web広告配信における多腕バンディット問題、Mortal Multi-Armed Bandits Problemとアルゴリズム - CARTA TECH BLOG
こんにちは@hagino3000です。Zucks Ad Networkという広告配信サービスの開発をしています。最近はアドネットワークの広告配信最適化に利用できるアルゴリズムの調査もしています。 本稿では調査で読んだ論文の一つ、オンライン広告配信を想定した多腕バンディット問題である、Mortal Multi-Armed Banditsを紹介します。多腕バンディット問題になじみがある読者を想定しています。 papers.nips.cc オンライン広告と多腕バンディット問題 ここでは簡単のために、クリック課金型のディスプレイ広告を前提に説明します。オンライン広告配信システムにおける問題として「最初はどの広告がどれだけクリックされるかわからないが、なるべくクリックされる広告を多く配信したい。」という物があります。これは多腕バンディット問題として知られており、探索はCTRが推定できるまで配信する事
最小カットについて - よすぽの日記
わっけわかんねえほど沢山の制約ドパァな問題を解く一般的なテクとして、 なんかいい感じのグラフを作ったらなんかそれの最小カットが答え というのがあります 最小カットで解ける問題はどんなのなのか考えてみました 頂点がたくさんあって、それを赤と青に塗り分けるという問題を考えます。燃やすと埋めるでも大丈夫です 最小カットで解ける問題というのは、実は 頂点がたくさんある。それを赤と青に塗り分ける。全部の頂点を必ず赤か青に塗らなくてはいけない 必ず赤色に塗らなくてはいけない頂点(Sとする)と青色に塗らなくてはいけない頂点(Tとする)が存在する 「Xが赤で、Yが青の時にZ円の罰金がかかる」という制約が沢山ある 罰金の最小値は？ という問題だけです。 これの解法は、 「Xが赤で、Yが青の時にZ円の罰金がかかる」ならX->Yに容量Zの辺を貼る SからTに最大流 流せた量が答え 処理できる条件は「Xが赤で、Y
「第2回 プログラマのための数学勉強会」開催しました！（動画＆資料つき） - 34歳からの数学博士
どうも、佐野です。 3/27(金)「第2回 プログラマのための数学勉強会」が開催されました。今回も多くの方にご参加頂き、数学愛ほとばしるセッションの数々をお送りできて嬉しく思っております。各セッションの動画・資料と共に、簡単に内容のご紹介をさせて頂きます。 1. 「プログラマのための線形代数再入門 2」 - 佐野岳人 [資料] 線形代数再入門の続編として行列式・逆行列について発表しました。高校や大学で行列式を習うときは低次の場合の計算法だけか、あるいは置換を使ったガチな定義を習うかのどちらかと思うのですが、「そもそもこれは何なのか」をプログラマが納得できるように、普段見慣れているであろう「要件・仕様・実装」のフォーマットでその意味と計算法について解説することを試みました。 数学科卒というと計算が得意とか暗算が速いとか思われがちですが、僕は自分でも悲しくなるほど計算が遅くよく間違います。掃き
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Sorting game
サルでも分かるwaifu2xのアルゴリズム.pdf - Google ドライブ
高速フーリエ変換
歌舞伎座.tech#4「コンピュータ将棋プログラミング」【山本一成】
色々なダイクストラ高速化
コスト行列とハンガリー法