東京工業大学でTarjan教授を拝見した - でも今日はSRMあるから
講義に出席した。顔を拝むのが目的。 Tarjan先生 我々が毎日書いているUnion-Findや強連結成分分解（lowlinkのやつ）の証明やらアルゴリズムやら考えたすごい人。 1時間の講義でZip Treeをマスターしよう。 Zip Tree 二分探索木の一つ。詳細な解説は講義に出た人の特権なので避けるがTreapにとても似ている。正直、名前聞いたことなかった。 Treapと比較して2つの違いがある ランク Treapはランダムな値を優先度としてノードに割り当てるがzip treeではそれをランクと呼ぶ。Treapでは経験上ノード1つに対してO(log n)ビットの追加メモリが必要だが、Zip TreeはO(log log n)ビット、多分。。。 実装ではこんな感じでいいだろうか？Treapのランクが32ビットなのに対し、Zip Treeは31以下（5ビット）で済んでいる。Treapで乱
Lock-freeとWait-freeアルゴリズム - Wikipedia
Lock-freeとWait-freeアルゴリズムとは、共有データにロックをかけてアクセスを防ぐアルゴリズムとは違い、複数のスレッドが同時並行的に、ある対象データを壊すことなしに読み書きすることを可能にするアルゴリズムである。Lock-free とはスレッドがロックしないことを意味しており、全てのステップにおいてシステムが必ず進行する。これはLock-free ではミューテックスやセマフォといった、排他制御のためのプリミティブを使ってはならないことを意味する。なぜならロックを持っているスレッドの実行が中断した場合、全体の進行を阻止しうるからである。Wait-free とは、他のスレッドの動作に関係なく、スレッドがいかなる操作も有限のステップで操作を完了させられることを指す。あるアルゴリズムがLock-freeであるがWait-freeでないことはありうる。Wait-free なアルゴリズム
chokudaiサーチのメモ - メモ
CODEVS 5で話題になったchokudaiサーチのリンク集 正式名は beam stack search だとか [追記２] ちょうだいさん本人のブログで解説されるのでそっちを読みましょう！ chokudai.hatenablog.com [追記] 診断人さん(@nico_shindannin)の調査によると、２つはアルゴリズムも目的も違うものであるとの指摘 shindannin.hatenadiary.com Beam stack search - Wikipedia] Chokudai search from AtCoder Inc. www.slideshare.net 説明 chokudaiサーチって何やねんって説明をある程度アルゴリズム解ってる人向けにすると、 ・幅1のビームサーチをする。この時、全部の過程と評価を残す ・残した評価から初手に戻り、幅2のビームサーチっぽいのに
Linear-time Kernelization for Feedback Vertex Set - wataの日記
https://arxiv.org/abs/1608.01463 が ICALP 2017 に採択されたので内容の解説をします． 概略 取り除くと残りが無閉路になる頂点集合を Feedback Vertex Set (FVS)と言い，与えられた無向グラフの最小FVSを求める問題をFVS問題と言います．これは有名なNP困難問題で，FPTアルゴリズムという理論アルゴリズムの研究分野で盛んに研究されており，PACE Challenge*1 というFPTアルゴリズムの実性能を競うコンテストの記念すべき第一回目 (2016年) の題材として選ばれました (ちなみに2017年のコンテストは 5/1 締め切りでまだ間に合うので興味のある方はぜひご参加ください)．この問題に対して，答えが$k$ (頂点数$n$に対してかなり小さいと想定)の時に $4^k n^{O(1)}$ 時間で動作するアルゴリズムを以前
Python SciPy : 線形計画問題を解く
適当な例を解いてみます。 linprog は目的関数を最小化するベクトルから解を求めます。 問題を目的関数の最大化としたい場合は式の係数の符号を反転させ、結果の符号も反転して読む必要があります。 import numpy as np from scipy.optimize import linprog c = [-3, -2] A = [[2, 1], [1, 1]] b = [6, 4] x0_bounds = (None, None) x1_bounds = (1, None) res = linprog(c, A_ub=A, b_ub=b, bounds=(x0_bounds, x1_bounds)) res fun: -10.0 message: 'Optimization terminated successfully.' nit: 3 slack: array([ 0., 0.
線形計画法のソルバの使い方：Python - Research Note！！
最近，線形計画法のソルバを使ってあれこれしました．使うために色々調べたわけですが，時間が立つと調べた内容を忘れそうなので記録しておきます． 線形計画法のソルバはPuLPというライブラリから呼び出して使います． PuLPインストール 方法は色々有るようですが，私の場合はコマンドプロンプトから， pip install pulpと打ってインストールしました． 例題を解いてみる こういう最適化問題があるとします． これは が答えなのですが，本当にそうなるかを試します． バッチ処理版 細かいところを説明する前に，まずは全体像をお見せします．バッチ処理で書くとこんな感じです． # (1)ライブラリ呼び出し import pulp # (2)問題の定義 lp = pulp.LpProblem('lp', pulp.LpMaximize) # (3)変数の設定 x1 = pulp.LpVariable(
組合せ最適化を使おう - Qiita
野菜の選び方はナップサック問題、乗り換え駅探索は、最短路問題といいます。典型問題は、よく研究もされているので、多くの場合、効率的な解法があります。あるいは、定式化がされているので、すぐ解くことができます。あとで、やってみましょう。ここで、あげている全ての典型問題の実行例は、典型問題と実行方法をご覧ください。 汎用問題 最近、私がやっているコンテナの仕事のお話しをします。 世界中の人たちが、いろいろなものを安く買えるのはコンテナ輸送のおかげです。中国などで生産したものを日本やアメリカやヨーロッパに、大量に安く運べるからです。でも、空のコンテナが、どんどんたまります。また中国に戻さないといけません。いつ、どこからどこに戻すかを決めるのが、最小費用流問題になります。ところが、最小費用流問題で表せない制約条件もあります。1 つが、カボタージュとよばれるものです。カボタージュというのは、国内のみの輸
子から異なる2つを選ぶ感じの木DPを解くアレ - よすぽの日記
子から異なる2つを選ぶ感じの木DPを解くアレを解くテクニックを紹介します。 D: Longest Path - Indeedなう（オープンコンテスト） | AtCoder とかが簡単に解けたりします 頂点0を根とする根付き木について 頂点iはa[i]を持つ(a[i] >= 0) 頂点iそれぞれについて、b[i] = a[i] + max(0, max(b[x] ただしxはiの子), max(b[x] + b[y] ただしx, yはどちらもiの子でかつx != y)) b[0]を求めよ という問題を考えます つまり、b[i]は子供から0, 1, 2個選んだ時のb[選んだ頂点]のsumのmaxにa[i]を足したものですね vector<int> g[MAX_V]; //g[p]は頂点pの子供を入れたvectorとする int a[MAX_V], b[MAX_V]; void dfs(int p
競技プログラミングにおける全方位木DP問題まとめ - はまやんはまやんはまやん
全方位木DP よく分かる解説 問題 CSA Connected Tree Subgraphs [解説 CF397 Tree Folding CF405 Bear and Tree Jumps AtCoder Driving on a Tree CSA Root Change EDPC Subtree 解説 CF Centroids 解説1 解説2 解説3 CF395 Timofey and a flat tree CF302 Road Improvement 解説 yukicoder No.768 Tapris and Noel play the game on Treeone 解説 違うけど方針が似ている問題 CF Nearest Leaf
CS Academy: Connected Tree Subgraphs - pekempey's blog
問題ページ modified 2018年12月21日 map を使ったこれはあやまりですので、キをつけてください。 modified 2018年12月17日 map を使うと書きやすいらしい。たとえば height を求めるには次のように書けばよい。 map<int, int> dp[100000]; vector<int> g[100000]; void dfs(int u, int p) { if (dp[u].count(p)) return; dp[u][p] = 0; for (int v : g[u]) if (v != p) { dfs(v, u); dp[u][p] = max(dp[u][p], dp[v][u] + 1); } } 解法 $O(n^2)$ 解法は TDPC の木という問題と同じ。 dp[v]:=vの部分木の番号の振り方を計算する。子が a,b,c,d だ
グラフとネットワーク - okamoto7の日記
明日から『グラフとネットワーク』という講義が始まるので，いろいろと思うことを書いておく． まず，このような授業をやることを依頼されて，それでシラバスとか考えて，立ち上がったわけだけども，この講義の名前が『グラフ理論』になりそうだったが，それは避けられた．もっとも，『グラフ理論』をやってもよいわけだし，私が『グラフ理論』の講義をすることもできるし，実際『グラフ理論』の講義もやったことがあるのだけれども，この『グラフとネットワーク』は「グラフ理論」の講義ではない．実際依頼された内容を考えれば『グラフ理論』などという名前を付けることは，学生に対して間違った印象を与えるだけで，害悪であるとさえ思える． よく大学の講義名に「○○」のあとに「理論」をつけて『○○理論』としてしまうものがあるが，それが本当に「○○理論」なのかどうかということを反省する必要がある．日本の大学において『グラフ理論』という名前
クリントン陣営が選挙運動のデータ分析に使っていた「Ada」アルゴリズムが敗北の原因か？
by Kristopher Harris 世論調査では優勢だったヒラリー・クリントン氏がなぜ選挙戦で負けたのか？ということについては、さまざまな分析がなされています。クリントン氏は選挙戦においてデータ分析を重視していたのですが、このとき分析に使われていたのが「Ada（エイダ）」によるアルゴリズム。Adaとは何なのか、なぜ正しい分析を出せなかったのかについて、The Washington Postが考察しています。 Clinton’s data-driven campaign relied heavily on an algorithm named Ada. What didn’t she see? - The Washington Post https://www.washingtonpost.com/news/post-politics/wp/2016/11/09/clintons-da
Googleの旅行アプリで使われている280年前のアルゴリズムとは？
By Celeste RC Googleが2016年9月20日にリリースした「Google Trips」は旅行に関する情報をまとめて管理できるアプリで、目的地までの移動方法や行き方、移動時間、観光地の場所や付近にあるレストランなど、さまざまな情報を元にして旅行の計画表を自動で作ることができます。Googleによれば、このGoogle Tripsに使用しているアルゴリズムは280年前のものを元にしているとのことで、その詳細をGoogleが公式ブログで明かしています。 Research Blog: The 280-Year-Old Algorithm Inside Google Trips https://research.googleblog.com/2016/09/the-280-year-old-algorithm-inside.html Google Trips - Google Pl
凸包の頂点数の話 - notブログ
まとめ のグリッドに収まる格子点を頂点とする凸多角形の頂点数は。 詳しい話は論文を読んでください。 On the maximal number of edges of convex digital polygons included into an m × m-grid はじめに 凸包を取ると考慮すべき点の数が減って嬉しい、という問題が競プロでたまに出題されます。 この類の問題の解説で頂点数のオーダーがと書いてあることがある*1のですが、実際はだよという話です。*2 方針 頂点数を大きくするにはマンハッタン距離が短い辺から使うのが最適です。 マンハッタン距離が以下の辺を使うと、頂点数がの凸多角形がのグリッドに収まります。 計算 めんどうなので、成分が正の部分だけ考えます。*3 そうすると使う辺は(1,1),(1,2),(2,1),(1,3),(2,2),(3,1),...となります。 これ
Interpolation - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
多項式補間に関して教えてもらったのでまとめておきます。 何らかのN次関数P(x)があったとします。xが小さい場合は簡単に計算できる時、それを利用して大きなxに対しても求めたいです。 連立方程式を解くと各項の係数が求められますが、O(N^3)掛かってしまいます。 それをO(N^2)にする方法の１つとして、ラグランジュ補間があります。 Qi(x) = (x-0)*(x-1)*...*(x-N) / (x-i) という関数を考えると、N次多項式は必ず、 P(x) = c0*Q0(x) + c1*Q1(x) + ... + cN*QN(x) という形で書けるそうです。 この関数Qの嬉しい所は、xにiを代入すると、Qi以外は全部0になって除去できる所です。 xにiを代入して考えると、係数ciはP(i)/Qi(i)となっており、簡単に計算できます。 各Qを求めるためにO(N)で、項がN個なので、O(N
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
PuLP による線型計画問題の解き方ことはじめ - Qiita
PuLP で数独を解く - Qiita
http://www.logopt.com/python_learning/wp-content/uploads/2014/05/mipproblem2.pdf
cakes（ケイクス）
Michael Garland - QSlim 2.0