様々な全域木問題
1. 2013 年 3 月 20 日 ＠ NTT DATA 駒場研修センター 第 12 回日本情報オリンピオック春季トレーニング合宿 様々な全域木問題 前原 貴憲 (@tmaehara) 国立情報学研究所 2. 自己紹介 • 前原 貴憲（まえはら たかのり） • Twitter: @tmaehara • Web: http://www.prefield.com (Spaghetti Source) • 略歴： 2004 沼津工業高等専門学校卒 2007 東京大学 工学部 計数工学科卒 2012 東京大学大学院 情報理工学系研究科卒 現在 国立情報学研究所 • 専門分野：連続・離散最適化，数値計算 2/ 71
グラフを切る - ita’s diary
「最高のカレーを作れ」問題 https://codeiq.jp/ace/yuki_hiroshi/q210 面白いです。別の例に例えると、128人の集団を２つの組に分けます。仲のいいペアは、なるべく同じ組になるようにしたい、という問題。 128個の粒子を用意して、仲のいい同士が引き合い、それ以外は反発するようにして動かすと以下のようになりました。 なんとそういう設問でしたか。集団を二つに切るなら、左の太線で切れば11組の好き同士を分断するだけで済みます。これがおそらく最適解。右が12本でわずかに違うところが絶妙。 確実に最適解を求めるアルゴリズムも、複雑だけどあります。以前の自分の日記から引用 最大流/最小切断定理 たとえば東京都内から筑波に人が一斉に移動するというシチュエーションを考える。東京に核ミサイルが落ちてきて筑波にシェルターがあるとか。このとき何時間で避難可能か、という問題を解く
モバイルゲームの歴史を年代別にご紹介します。モバイルゲームの成長と今後について詳しく解説していきます。
モバイルゲーム 物凄い勢いで勃興したモバイルゲーム業界は、いろいろな課題や問題に直面しながらも巨大化し、今日の時点でのスマートフォン向けゲームの市場へと継承されていきます。 モバイルゲームの歴史 2001 Javaアプリと3Dゲームの登場 Javaが利用できるようになったことにより、ダウンロード型のゲームが供給できるようになりました。 2002 携帯電話端末の大容量化・3D化競争 Java搭載携帯電話端末が登場してからごく僅か1年の間に、アプリのサイズに関しては10倍に広大化し、表現方法も2Dから3Dにシフトし始めました。J-PHONEは『ゼビウス』や『スペースハリアー』などといった昔のアーケードゲームを、ドコモはSIMCITYなどパソコンで世界的規模のヒットを飛ばしたゲームを主力商品としていました。 2003 モバイルゲームの一般化 メモリの制限が厳しいJava仮想マシン上ではなく、OS
ウェーブレット木の効率的で簡単な実装 "The Wavelet Matrix" - EchizenBlog-Zwei
久しぶりに論文を読んだ。 http://www.dcc.uchile.cl/~gnavarro/publ.html The Wavelet Matrix Claude & Navarro; SPIRE2012 "The Wavelet Matrix"はSPIRE2012のNavarro無双のうちの一本。タイトルからするとウェーブレット木の拡張のように思える。 機能としてはウェーブレット木と同一でデータ列に対するaccess,rank,selectを提供する。しかし実装は既存手法と比べて効率的でしかも簡単になっている。 これまでにウェーブレット木の実装としてはノードをポインタでつないだ普通の木として実装する方法(Standard Wavelet Tree. 論文のAlgorithm 1)と、木の階層ごとにノードをつなげた配列で表現する方法(Levelwise Wavelet Tree. 論文
中学生にもわかるウェーブレット行列 - アスペ日記
id:echizen_tm さんの記事「ウェーブレット木の効率的で簡単な実装 "The Wavelet Matrix"」から始まったウェーブレット行列ブームから半年以上が過ぎ、すでに枯れた技術として確立されつつある感があります。 …嘘です。 日本以外ではあんまり来ていません。 理由としては、やはりアルファベット圏では単語境界が明確であるため、こちらの記事で書かれているような「キーワード分割の難易度」といったことがあまり問題にならないということがあるかもしれません。 まあ、そういうわけで局所的に来ているウェーブレット行列ですが、日本語をはじめとする単語境界のない言語圏にとっては重要なネタであると思うため、解説記事を書き直して*1みようと思います。 ウェーブレット行列でできること 主となる操作は、文字列に対する 定数時間の rank() と select()*2 です。 rank() は、「文
指数時間アルゴリズム入門
2. 自己紹介 TopCoder: ◎wata TCO2010Marathon優勝など Twitter: @wata_orz 東京大学情報理工学系研究科コンピュータ科学専攻 理論計算機科学 (アルゴリズムの理論的な解析とか) プログラミングコンテスト チャレンジブック 2 3. 本日の内容 NP困難問題を解くためのアルゴリズムを扱います 𝑂𝑃𝑇 𝐼 ≤ 𝐴 𝐼 ≤ 𝑐𝑂𝑃𝑇(𝐼) 近似アルゴリズム ヒューリスティック 𝑓 𝑘 𝑝 𝑛 FPT アルゴリズム max 𝑐𝑥|𝐴𝑥 ≤ 𝑏, 𝑥: 整数} { 𝑂∗ 𝑐 𝑛 整数計画 厳密指数時間アルゴリズム 3 4. 効率的な指数時間アルゴリズム 何の指数？ 頂点数? 辺の数? それとも… • 2 𝐸 のアルゴリズムはまず役に立たないが，2 𝑉 のアル ゴリズムならコンテストでもよ
Stackを使ってQueueを作る - くまメモ
有名な話かと思ったら意外と知られていなかったのでメモ。 FILOを使ってFIFOを作るとも言います。StackでQueue作れてもQueueでStackを作る方法が思いつかないので誰か教えて下さい。もしくはこういう学問があったら紹介して頂けると嬉しいです。 簡単な説明としては、2つのStackを用意して、enqueueするときには1つ目にpush()し、dequeueするときには2つ目からpop()するだけ。 ただし2つ目のStackが空の場合は1つ目のスタックが空になるまで2つ目のスタックに移し替える。 template<typename T> class MyQueue { std::stack<T> in, out; MyQueue(){} void enqueue(const T& v) { in.push(v); } T dequeue() { if (out.empty())
ウェーブレット木を試す - Negative/Positive Thinking
はじめに 巨大な文字列でも高速にクエリ処理できる噂の木を、挙動を確認するため作ってみた。 コード アルファベット(a〜z)の文字列を扱う場合 完備辞書の操作が愚直、ビット列がvector 本を参考にしたけど、2か所間違ってる？ #include <iostream> #include <vector> #include <queue> #include <cmath> //top_kのためのタプル struct ST { int t; size_t st, en; ST(int t, size_t st, size_t en):t(t),st(st),en(en){} }; bool operator<(const ST& a, const ST& b){ return (a.en-a.st) < (b.en-b.st); } //アルファベット([a-z]+)用のウェーブレット木 cla
TCO Round1B - 不定期プログラミング覚え書き
結果報告 今回はちゃんと寝ブッチしなかった！ 会社の寮からテザリング参加。夕方頃お酒飲んでたけど流石に25時には酔いも冷めてた 250-500-1000回。 Level ProblemName Status Point Easy FoxAndKgram PassedSystemTest 209.24 Medium FoxAndDoraemon PassedSystemTest 372.26 Hard FoxAndPhotography Opened ---- Easy FoxAndKgram 問題 色々な長さの鉛筆がある． これらの鉛筆を使って（全部使わなくても良い），K-gramという図形を作りたい． ある自然数Kに対して，K-gramとは， 長さKの鉛筆からなる行 二つの鉛筆を長さ１だけ開けて置いた行．鉛筆二つの長さの和+1＝Kを満たす． を満たす，K行の図形である． 鉛筆の長さを配列
ライフゲームの世界 - 人工知能に関する断創録
ニコニコ動画の複雑系コミュニティの発起人のはむくんがライフゲームの世界というとても面白い動画を投稿されています。Twitterでは何度かツイートしてたけど完結したのでブログでも紹介させていただきます。 ライフゲームの世界1 John Horton Conwayが提案したライフゲーム（Conway's Game of Life）の基本的なルールを解説しています。また頻繁に現れる4種の物体（ブロック、蜂の巣、ブリンカー、グライダー）を紹介しています。最後の作品紹介は、P416 60P5H2V0 gunというすさまじいパターンが出てきます。グライダー銃から発射したグライダーたちが滑走路を通ります。グライダーの集合先では、発射された複数のグライダーが合体して宇宙船が組み立てられます。 ライフゲームの世界2 いろんな振動子（パルサー、タンブラー、銀河）が鑑賞できます。作品紹介では大量の振動子が勢揃い
「高速文字列解析の世界」を読む前に知っておくと良いこと - EchizenBlog-Zwei
「高速文字列解析の世界」という大変すばらしい本が発売された。わりと敷居が高い本ではあるので読む前に知っておくとよさそうなことを書いておく。 「高速文字列解析」とは 本書でいう高速文字列解析というのは主に2つのことを指している。ひとつはデータを圧縮して小さくしてディスクよりメモリ、メモリよりキャッシュというようにより高速な記憶装置で扱いましょう、という話。もうひとつはデータ構造を工夫することで複雑な操作もそこそこ高速に扱えますよ、という話。つまり「圧縮」の話と「効率的なデータ構造」の話があると考えておくと良い。 キーワードは3つ オビにも書いてあるけれど、本書が主に扱うのは「BWT」「簡潔データ構造」「ウェーブレット木」の3つ。具体的には「BWT」が「圧縮」に関わっていて「ウェーブレット木」が「効率的なデータ構造」に関わっている。「簡潔データ構造」は基本的な道具として本書の色々なところで出て
機械学習と自然言語処理とビッグデータ - Preferred Networks Research & Development
岡野原です。 情報処理学会主催の連続セミナー「ビッグデータとスマートな社会」での機械学習の回、自然言語処理の回での講演資料を公開しました。 今年はビッグデータという言葉が広まったということで、このテーマで話す機会が多かったです。今はビッグデータというとそれを支えるインフラ、クラウド、DBなどがまず注目されていますが、我々としては実際それを使って何をするのか、何が実現できるのかというところを注目しています。 PFIは元々こうしたデータを分析して価値を提供する（検索エンジンとかもその範疇に入ると思います）ことをずっと続けてきたわけですが、ビッグデータという言葉が広まってくれたおかげでこの考えがより受け入れられ様々な業界の方と随分と話がしやすくなったと思います。 以下の講演資料では、今ビッグデータの中でも機械学習と自然言語処理の分野において我々がどこに注目しているのかを話をしました。
構造化『並列』プログラミング - どらの日記
構造化プログラミング。 といえば、順次、分岐、ループのパターンからなる、シリアルプログラミングにおける基本スタイルですね。（これらだけしか使わなくてもシリアルプログラムは書けますっていうね） C++にはあらかじめこれらのパターンを簡単に使えるようにシンタックスが用意されています。 分岐はifやswitch、ループはwhile、for、doといったかんじで。 もちろんこれらのパターンは並列プログラミングでも使えます。 しかし並列プログラミングにおいては、これらのパターンだけで実装を行うことはほぼ不可能です。 そこで、並列プログラミングにおけるパターンとなる構造が考えられてきました。 これらを使うことで、よりパワフルかつ簡潔に並列プログラムのコードを書けるようになります。 １．マップ もっとも基本的な並列パターンです。 まず、コードを見てください。 template <class T> voi
焼きなまし法のコツ Ver. 1.2 - じじいのプログラミング
↓改訂版 Ver1.3はこちらから↓ shindannin.hatenadiary.com 2016年8月18日 Ver. 1.2 内容を更新しました。 4.遷移確率と温度の部分を全般的に修正 この記事は、Competitive Programming Advent Calendar Div2012の24日目の記事です。 http://partake.in/events/3fcea6d7-0bab-4597-82db-86439aadb1b9 素晴らしい企画をしていただいたtanzakuさん（https://twitter.com/_tanzaku_）、今年もどうもありがとうございます！ 焼きなまし法そのものの解説は少しだけにして、焼きなまし法の使い方のコツをメインに書こうと思います。 焼きなまし法の概要 2015年5月26日 内容を更新しました。 最適化（=最大値か最小値を求める）の手法
Bitwise Tricks & Techniques - Darseinのプロコン日記
この記事はCompetitive Programming Advent Calendar Div2012、20日目の記事です。(余談：そういえば本日2012/12/20は良い日ですね！) はじめに 今回はDonald.E.Knuth著”The Art of Computer Programming”のVolume4-1の前半パートであるBitwise Tricks & Techniquesで取り上げられているビット演算について記事を書きたいと思います。ただし、ここで取り上げられているものは必ずしも競技プログラミングにおいて実用的とは限りません。すでに関数として定義されているものはそれを使った方が実装量が減らせてよいと思います。なので、「ビット演算やべぇおもしれぇ！！」と思ってもらう一助となることを目指した読み物、という感覚で読んでいただけると幸いです。 今回はC++言語を基本としてコードを
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Quickhull 3D | Heinrich Fink
組合せ最適化入門：線形計画から整数計画まで
std::minmax_element - cppreference.com
ハル研究所 プログラミングコンテスト2012｜結果発表
ウェーブレット木の世界 - Preferred Networks Research & Development