ALENEX'14 に論文採択 - iwiwiの日記
国際学会 ALENEX 2014 に論文が採択されました．ALENEX (Meeting on Algorithm Engineering & Experiments) は SIAM によって開催される実験系アルゴリズム (experimental algorithmics) を扱う最も有名な会議の 1 つで，理論系アルゴリズムのトップ学会 SODA (Symposium on Discrete Algorithms) に併設して開催されます．発表は来年の 1 月にアメリカのオレゴンです． 今回の論文は "Fast Shortest-path Distance Queries on Road Networks by Pruned Highway Labeling" というタイトルで，研究室の後輩の河田君，同期の岩田，NII の河原林先生との共著です．タイトルからご察しの通り，SIGMOD'
Typical DP Contest : J - ボール - kmjp's blog
期待値系の問題、苦手なんだけどこれ落ち着いてやれば本番でも解けたな…。 http://tdpc.contest.atcoder.jp/tasks/tdpc_ball 問題 座標0～15の整数値のいくつかに的がある。 座標xにボールを投げると、(x-1)、x、(x+1)の場所のいずれかに当確率で到達する。 すべての的を倒すまでのボールを投げる回数を答えよ。 解法 座標の範囲を見ただけでBitDPだとわかる問題。 残されたボールをbitmap表現したときの期待値を、それより小さいbitmapの期待から求める。 座標(x-1)、x、(x+1)のいずれかに的があるなら、xにボールを投げる価値があるので、その時の期待値を求める。 1<=x<=14の範囲で期待値を最小化する値を求める。 期待値の求め方は毎回戸惑うので整理しておく。 bitmapがxの時の期待とをF[x]とする。 たとえば残されたボール
蟻本P191 最大流 - 最小カット定理 - WARush
蟻本に載ってることそのまま書くだけ 蟻本の最大流で使われたグラフをそのままサンプルで使います。 ↓↓ グラフのカットとは、ある頂点集合Sに対して、Sから出ていく辺の集合の事をいい、 カット(S V/S)のように表します。また、その辺の容量の和をカットの容量といいます。 さらに、Sの中にsを、V/Sの中にtを含むようにカットすることを、 s-tカットといいます。 最小カット問題とは・・・ ネットワークにに対して、sからtへのパスが存在しなくなるために（つまりs-tカットで） 除去しなければいけない辺の容量の和の最小値はどれだけか という問題である。 フロー流量とカット容量の関係 まず、任意のs-tフロー f と任意のs-tカット(S, V/S)を考えてみましょう。 ↓こんなフローとカット↓ sについては( fの流量 ) = ( sから出る辺の流量 )であり、 それ以外のSの頂点vについては(
情報幾何学講義 【チャンネルA】
甘利俊一先生 情報幾何学講義 （チャンネルA) 統計数理研究所 夏期大学院 の講義のうち 甘利俊一先生の担当部分を配信しました。 当分の間、録画を公開する予定です。 投影資料は http://www.ism.ac.jp/shikoin/summer-school/2013.html のリンクからダウンロード可能です。 なお、以下のうち、スマートフォンや一部のタブレットでは1のみしか視聴できません。2,3は配信時にブロードキャスターを使ったためで、これはUSTREAM側の仕様のようです。お手数ですがPC・マックからの視聴をお願いします。 【甘利先生講義１ 午前冒頭】 録画のトラブルで欠けていた最初の部分を別の録画から補充しました。配信技術未熟のため冒頭に空白が、また末尾にループして冒頭がそれぞれ少し入っておりますがご容赦ください。この冒頭部分では講師の表情をとらえることに主眼をおいた撮影をし
数え上げ問題集 ver.0 - tozangezan's diary
数え上げ問題集 数え上げの問題をある程度まとめます。といっても多すぎて面倒なので、まとまって存在するものはリンクを張ります。 また、検索の都合上「答えを1000000007で割った余りを求める」以外の形式の数え上げは見落とされがちなので、そこらへんは割り切ってください。 まとまって存在するリスト(数え上げをたくさん解きたい人用) http://codeforces.com/problemset/tags/combinatorics 数え上げばっかり集めてあります http://community.topcoder.com/tc 多すぎる上ローカルに保存してなくて調べるのが面倒なので、自分で調べてください。 参考までに、感じる難易度をTopCoder Div1の点数に換算して書いておきます。 良問には☆をいくつか付けます。 AOJ 2333 (500) ☆ AOJ 2335 (650) AO
クッキーの生産が下手な男の人は仕事も出来ない
IT企業に勤めてるせいか、昼休みに一部でブームになってる例のクッキーの話になった。 みんな結構はまってるみたいで、各々のcps(一秒間にできるクッキーの量らしい) を言い合うみたいな流れになったんだけど、驚いたのが、仕事の出来る男の人と そうでない人で全然cpsが違うってこと。なんかもう、すっごく大きい差がついてる。 私はツイッターで話題になってるのを知ってるぐらいで自分でプレイはしてなかったから、 なんでそんなに差がつくんだろうと思って色々と聞いてたら、人によってプレイの方法に 違いがあるってことに気づいた。 仕事が出来る人は、どういうルールのゲームなのかというのをちゃんと考えて戦略的に クッキーを増やすようにプレイしてるみたい。 反対に仕事が出来ない人は場当たり的に施設みたいなのをアップグレードしてるらしい。 同じゲームをプレイしてるはずなのに、cpsの大きい人と小さい人では全然見えて
PEGWiki
Hello, World! Welcome to PEGWiki! This is the informational part of the website of the Woburn C.I. Programming Enrichment Group (PEG); the functional part, our online judge, is located here. This wiki has the following aims: to contain all interesting information about our organization, including but not limited to our goals, members, upcoming events, up-to-date news, achievements, memories, and t
A Survey of Monte Carlo Tree Search Methods
// Join our awesome newsletter! * You can also place any other content here
Monte Carlo Tree Search - Home
Welcome to the Monte Carlo Tree Search (MCTS) research hub. The aim of this site is to provide a convenient reference point for MCTS material on the internet, to aid researchers in the area. This is an initiative of the £1.5m EPSRC project UCT for Games and Beyond. Please to submit corrections and additions. Crazy Time is Evolution Gaming's popular game show with a Money Wheel of Fortune and four
マルコフ連鎖モンテカルロ法を実装してみよう
"Chain Bridge, Budapest" by szeke 約2ヶ月ぶりということで、ご無沙汰しております。書きたいネタというのは結構あって書こう書こうとは思っているんですが、なにより書くとなるとあれもこれも伝えなきゃいけないみたいな思いになって、結局分量の多さから諦めてしまうというのが結構続いています。もう少し気を張らずに更新していきたいものです。 さて、最近の自分はマルコフ連鎖モンテカルロ法(Markov Chain Monte Carlo, MCMC)についておりました。何にも知らない方ににとってはよく分からないかもしれませんが、この手法はマルコフ連鎖が持つ簡明さとモンテカルロ法が持つ実用性が合わさった凄まじい手法なんです。そしてなによりとてもエレガント。 とりあえず知らない人のためにてきとーに解説しますと、与えられた適当な関数から確率変数をサンプリングするための公式です。べ
Algorithm And Tips For Competitive Programming
3.3 高速化 以下のコードをmain関数の最初に書くことで、cin,coutの速度が2倍程度になる。 ios::sync_with_stdio(false); cin.tie(0); ただし、このコードはstdioとの同期を切るという意味なので、これを使うとき にはprintfやscanfを使用してはだめ。 4 std::vector ここでは、配列のSTL版である、vectorの使いかたについて書く。 ここに書かれている関数は、string等にも用いることができるものが多い。 ちなみに、vector<bool>は使ってはいけない。bitsetや、vector<char>をつかうこと。 また、all(vector)は、vector.begin(),vector.end()とdefineしている。 4.1 基本 //要素数10で、初期値は-1にする。 vector<int> vec(10,
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
CODE VS 2.0 連鎖のキホン
CODE VS 3.0 サンプル動画
まーす on Twitter: "http://t.co/cceVWtzMVZ 2部グラフでの|最大マッチング| = |最小点カバー| の証明が図と共に示されててわかりやすかった"
まーす on Twitter: "http://t.co/QAUTgWmBYZ 最大安定集合と最小点カバー,2部グラフについてわかりやすかった"
いしはた まさかず on Twitter: "おねえさん…。：“「おねえさんの問題」の最先端 -YouTube動画と世界記録-” http://t.co/2MRiipJ60M"
Numpla2
Ideone.com
IBM Developer
高速な最近某探索