動的計画法によるDVDのディスク分割の改善
こんにちは。「家族アルバム みてね」の開発チームに所属している黒川と申します。今回は、その「みてね」の機能の1つで、写真や動画をDVDにして注文できる機能を動的計画法を使って改善した話をします。 「みてね」では家族の写真や動画をアップロードし、アプリ上で月ごとに振り返ることが可能になっています。一方、たとえば自宅のテレビやパソコンでまとめて振り返りたいという要望もあり、「みてね」では最長過去1年間の写真や動画をDVDにまとめて注文することができます。 このときに問題となるのがDVDのディスク分割です。1年分の写真や動画はともすると1枚のディスクに収まりきらず、複数のディスクに分割する必要があります。いままでは、動画を月ごとに分けて各ディスクに入れていく、というシンプルなアルゴリズムで分割を行っていました。しかし、ユーザーさんからは「1枚のディスクにすこしの動画しかないがどうなっているのか」
動的計画法を実現する代数〜トロピカル演算でグラフの最短経路を計算する〜 - Qiita
トロピカル半環と呼ばれる代数構造上のトロピカル行列を利用すると動的計画法を使ってグラフの最短経路の距離を計算するという問題が単純な行列積で解けてしまうらしい。そんな噂12を聞きつけて我々はその謎を解き明かすべく南国（トロピカル）の奥地へと向かった。 トロピカルな世界に行くためにはまずは代数を知る必要がある。要するに群・環・体の話だ。しかしこの記事の目的は代数学入門ではないので詳しい話は他の記事3に譲るとし、さっそく半環という概念を導入する。それは 半環は以下の性質を満たす二つの二項演算、即ち加法（和）"$+$" と乗法（積）"$\cdot$" とを備えた集合$R$を言う $(R, +)$ は単位元 $0$ を持つ可換モノイドを成す: $(a + b) + c = a + (b + c)$ $0 + a = a + 0 = a$ $a + b = b + a$ $(R, \cdot)$ は単
手を動かして読む技術書のススメ なっとく！アルゴリズム｜まりーな／エンジニア
実際手を動かしてみて思ったのだが、３章で使った内容を４章でも発展して使い、そして５章でさらに発展させるという形で段階的にわかるようになっている構成であることに気がついた。手を動かしてみないとわからないものである・・。 ●練習問題がある 章の終わりに練習問題がある。コレの良いところは、一つに付き2~5分くらいで終わること。たくさん時間がかかると本章だけで、挫折しそうになるのに、問題がいい感じに軽いというところが乗り越えられるポイントだった ●気になっていたアルゴリズムが紹介されていた。 ナップザック問題や巡回セールスマン問題。名前は聞いたことあるけど、具体的にどうやって解くのか知らないという問題を絵付きで解き方が紹介されていてよかった。 ●メモリの仕組みビックオー記法と配列とリンクリストの紹介 どうしたら早くなるかという話だけじゃなくて、そもそもどうして遅くなるのか、どうやって値が保存されて
EMアルゴリズム徹底解説 - Qiita
本ブログは、混合ガウス分布を題材に、EMアルゴリズムという機械学習界隈では有名なアルゴリズムを丁寧に解説することを目的として書いています。 また、この記事は、「数学とコンピュータ Advent Calendar 2017」の24日目の記事です。 そして長いです。 1. はじめに 観測した確率変数 $X$ をよく表現する、モデル $p(x|\theta)$ のパラメータを求めることが確率分布の推定ではよく行われます。つまり最尤法ですね。より複雑な分布になるとその分布の構造に潜在変数(Latent Variable) $Z$ があると仮定してモデル化を行うと、シンプルな組み合わせで $X$ の分布を表現できることがあります。今回扱う混合ガウス分布もその一つです。 のちに説明しますが、データセットの種別を完全データ集合と不完全データ集合に分けた場合、不完全データ集合に属するようなデータセットはデ
【Python】 Constant-Q 変換 (対数周波数スペクトログラム) - 音楽プログラミングの超入門（仮）
関連記事 高速な Constant-Q 変換 【Python】 高速な Constant-Q 変換 (with FFT) - 音楽プログラミングの超入門（仮） 導入：対数周波数スペクトログラム Pythonで短時間フーリエ変換（STFT）と逆変換 - 音楽プログラミングの超入門（仮） 上記の記事で，音響信号を周波数スペクトルの時間変化を表すスペクトログラムに変換する短時間フーリエ変換を扱いました．簡単にアルゴリズムを復習すると，音響信号を一定の幅で切り取ってフーリエ変換するという処理を少しずつずらして行っていくことでスペクトログラムを得ていました． ここで，音響信号を一定の幅で切り取ってフーリエ変換するということについて少し考えてみましょう．切り取られた信号が以下のようなものであることを考えます． 窓幅が 256 サンプル(fs=4[kHz])で、ここでは信号を 1000[Hz]，400[
ソートアルゴリズムを極める！ 〜 なぜソートを学ぶのか 〜 - Qiita
NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。 今回はソートについて記します。 0. はじめに データ構造とアルゴリズムを学ぶと一番最初に「線形探索」や「ソート」が出て来ます。これらのテーマは応用情報技術者試験などでも頻出のテーマであり、アルゴリズムの Hello World とも呼ぶべきものです。 特にソートは、 計算量の改善 ($O(n^2)$ から $O(n\log{n})$ へ) 分割統治法 ヒープ、バケットなどのデータ構造 乱択アルゴリズムの思想 といった様々なアルゴリズム技法を学ぶことができるため、大学の授業でも、アルゴリズム関連の入門書籍でも、何種類ものソートアルゴリズムが詳細に解説される傾向にあります。本記事でも、様々なソートアルゴリズムを一通り解説してみました。 しかしながら様々な種類のソートを勉強するのもよいが、「ソートの使い方」や
NUPSC招待講演：アルゴリズムで広がる世界
「金融予測アルゴリズムを評価するときに、あまり一般的ではないけども自分としては皆に気にかけてほしいこと」を伝えたいと思い MarketTech Meetup #01 (https://alpaca.connpass.com/event/108066/) で話したときのスライドです
計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜 - Qiita
NTT データ数理システムでリサーチャーをしている大槻 (通称、けんちょん) です。今回は計算量オーダーの求め方について書きます。 0. はじめに 世の中の様々なシステムやソフトウェアはアルゴリズムによって支えられています。Qiita Contribution ランキング作成のために用いるソートアルゴリズムのような単純なものから、カーナビに使われている Dijkstra 法、流行中のディープラーニングに用いられている確率的勾配降下法など、様々な場面でアルゴリズムが活躍しています。アルゴリズムとはどんなものかについて具体的に知りたい方には以下の記事が参考になると思います: アルゴリズムとは何か ～ 文系理系問わず楽しめる精選 6 問 ～ アルゴリズムを学ぶと $O(n^2)$ や $O(n\log{n})$ や $O(2^n)$ といった計算量オーダーの概念が登場します。こうした記法を見ると
AtCoderで水色になるまでにやった事とかをまとめる - shibh308’s diary
こんにちは。3/17のABC091で無事水色になる事ができたので、今までにやってきた事と水色になるために必要だと感じた事をまとめようと思います。 この記事に載っている内容はあくまで個人の意見なので、あくまで参考程度にお願いします。 また、私自身が水色最底辺の人間なので知識が浅く、いくつか間違っている点があるかもしれません。ご容赦ください。 自分語り 塚本@shibh308です。執筆時点でのレートは1215で、今までのレート推移はこんな感じ(下画像参照)です。 競技プログラミングを本格的にやり始めたきっかけは去年の12月ごろ、JOI予選で300点爆死をキメたのがきっかけでした。当時はアルゴリズムについての知識が全くなかったので、200点問題ですら解けるか怪しいようなレベルだったと記憶しています。 当時のコードはこんな感じですね。この時はB問題を時間いっぱい使ってやっと解けたみたいな状態でした
お天気プロコンと圧縮アルゴリズムについて - 兼雑記
https://beta.atcoder.jp/contests/wn2017_1/standings むっちゃ僅差で2位。残念。この212点差がどのくらい僅差かというと、最後にいじってたところにもう2行変更を入れることを思いつけていれば、軽く2000点は差がついて勝ててたと思いますし、そうでなくても後30分もあれば実装できた細かいヘッダの圧縮で逆転できた量です。自分に悔しがる気持ちというのがこれほど残ってたのか、と驚くほど悔しいです。でも勉強になったし楽しかったです。 やったことを書きつつ、そもそも圧縮アルゴリズムについて、私としては感動的だった知見を得られたので、書いてみようかと思います。 今回のコンテストは、チャンネル1つの(RGBじゃなくてグレースケールだと思えば良い)画像を64枚を可逆圧縮するというものでした。その64枚の画像は同じ座標について光の波長と時間を変えて気象衛星が観測
トップIT企業にソフトウェアエンジニアとして就職するためのプログラミング能力 - 俺とプログラミング
Google, Apple, Microsoft, Amazon, Facebook, Twitter, IndeedなどのトップIT企業のコーディング面接で要求されるプログラミング能力について紹介します。これらの外資IT企業では、面接でホワイトボードでのコーディングが要求されます。私はこれまでに上記企業を含む数社で十数回ほどコーディング面接を経験しました。その経験を元にして記述しましたので、これらの企業に入社したい人にはある程度有用な記事になっていると思います。 日系企業だと、楽天，Line、リクルート、サイバーエージェントなども選考過程にプログラミングテストがありますが、外資企業とは少し出題形式が違います。おまけとしてそれぞれ簡単に紹介します。なお、ここで紹介しているプログラムは実装の一例に過ぎませんので悪しからず。 この記事を読む前に 求められる水準について コツ データ構造 事前準
差分検出アルゴリズム三種盛り - Object.create(null)
こんばんは. 気がつけばもうずいぶんと涼しくなってきました. 勢い余って凍ってしまったりせぬよう, くれぐれも普段の言動にはお気をつけください. はじめに さて, 我々人類にはどうしても二つの文字列 (あるいは行ごとに区切られたテキスト) 間の差分を求めなければいけない瞬間が発生します. 先人たちはそういった時のために diff のようなツールを開発し, それを利用することで文明はめざましい発展を遂げてきました. しかしながら, 使用するアルゴリズムを比較検討したい場合, 「差分」の定義を変えるなどして既存のアルゴリズムに変更を加えたい場合, diff のない異世界に飛ばされて自分で実装しなければいけない時などにおいては, 差分検出アルゴリズムについての理解が必要不可欠です. というわけで, この記事では文字列間の差分検出とは何かということと, 差分を求める三種類のアルゴリズムの紹介・解説
Deep Learningによる一般物体検出アルゴリズムの紹介 - ABEJA Tech Blog
一般物体検出アルゴリズムの紹介 今回CNNを用いた一般物体検出アルゴリズムの有名な論文を順を追って説明します。 コンピュータビジョンの分野において、一般物体検出とは下記の図のように、ある画像の中から定められた物体の位置とカテゴリー(クラス)を検出することを指します。 [6]より引用 Deep Learningアルゴリズムの発展によって、一般物体認識の精度は目まぐるしい勢いで進歩しております。 そこで今回はDeep Learning(CNN)を応用した、一般物体検出アルゴリズムの有名な論文を説明したいと思います。 R-CNN (Regions with CNN features) (CVPR 2014) [1] かの有名なCNNの論文[8]で、ILSVRC 2012の物体認識チャレンジで大差をつけて1位になりました。 このチャレンジでは1枚の画像が1000クラスのうちどれに属するかを推定する
フィルタサイズに対して定数オーダーの計算量のmin/maxフィルタを実現するvan Herk/Gil-Wermanアルゴリズム - Qiita
フィルタサイズに対して定数オーダーの計算量のmin/maxフィルタを実現するvan Herk/Gil-WermanアルゴリズムPythonalgorithmImageProcessing はじめに 入力信号に対し、あるフィルタサイズでmax/minをとっていくような処理が必要なケースがある。一番のユースケースは、画像処理におけるdilation（膨張）やerosion（収縮）処理である。個人的には、昔、ある幅を持ったnon-maximum suppression処理を行うために実装したことがある。 この処理は、ナイーブに実装すると信号長×フィルタサイズのオーダーの計算量が必要となるが、信号長のオーダーの計算量に抑えることができる「van Herk/Gil-Wermanアルゴリズム」というものが存在し、なるほどーという感じなので紹介する。 なお、長い信号に対してあるフィルタサイズのmin/m
三目並べで学ぶミニマックス法 | POSTD
最近、「絶対に勝てない三目並べ」のゲームを作ったのですが、非常にささやかながらも楽しいプロジェクトで、いろいろ学ぶこともできました。ゲームの全体像に興味がある方は、 こちらでゲームを試してみてください 。 無敵のゲームにするには、コンピュータ側が全ての手を計算し、何らかの基準を用いて最善の手を決められるようなアルゴリズムを作る必要があります。多岐にわたって調べた結果、このプロジェクトにはどうやら ミニマックス アルゴリズムが適当そうだということが分かりました。 このアルゴリズムを根本的な意味で真に理解し、自分のゲームに実装できるようになるまでにはある程度の時間が必要でした。多くのコードサンプルと説明に目を通しましたが、私が能なしだからか、どれを見てもプロセスの内実を十分に理解することはできなかったのです。この投稿が、ミニマックスアルゴリズムに関する皆さんの理解に少しでもお役に立てたらと思い
最小全域木問題(クラスカル法とプリム法) - ぬいぐるみライフ？
最小全域木問題を解くためのアルゴリズム「クラスカル法」と「プリム法」を使ってみた． 最小全域木について クラスカル法 プリム法 PKUの問題 クラスカル法による解答 プリム法による解答 メモリ使用量と実行時間の比較 最小全域木について まず，全域木(Spanning tree)とは連結グラフの全ての頂点とそのグラフを構成する辺の一部分のみで構成される木のこと．つまり，連結グラフから適当な辺を取り除いていき，閉路をもたない木の形にしたものが全域木となる．ここで，グラフの各辺に重みがある場合，重みの総和が最小になるように辺を選んで作った全域木のことを最小全域木(Minimum spanning tree)という． 最小全域木を求めるアルゴリズムとしては以下の二つが有名である． クラスカル法 (Kruskal's algorithm) プリム法 (Prim's algorithm) いずれも貪欲
Imos法(いもす法) - sataniC++
概要 累積和を用いて複数の要素の重なり・深さなどを計算します。 使える状況 括弧のみの文字列("((()(())))"など)の括弧の深さや、ある場所への人の出入り時刻がわかっているときの最多人数など、複数の要素がどれだけ重なっているかを効率よく調べるときなどに使うことができます。 説明 概要にあるような「複数の要素の重なり」を計算するときは、単純に考えると、 ”各要素について範囲内のカウントを足す” という方法を考えることが出来ます。このとき、計算量は 要素の個数範囲の長さ となりますが、それよりももっと早い方法があります。それがいもす法と呼ばれるアルゴリズムを使う方法です。 いもす法では、基本となる配列に「」や「」といった前のデータとの差分を入れておき、その配列の累積和をとることで同様の結果を得ることが出来ます。 このときの計算量は 要素の個数範囲の長さ と、先ほどよりも結構小さくなって
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
双対性
整数論テクニック集 - kirika_compのブログ
http://arxiv.org/pdf/1712.01208v1