AHC020でシュタイナー木を作るような問題がでました。そこでプリム法ベースのシュタイナー木を作ることがあったのでその方法を説明します。 シュタイナー木とは グラフとターミナルと呼ばれる頂点集合が与えられたとき、ターミナルを全てつなぐ木のことをシュタイナー木といいます。 頂点A,B,Cがターミナル シュタイナー木の例 ターミナルでない頂点はつないでもつながなくても構いません。 シュタイナー木のうちコストが最小のものを最小シュタイナー木といい、これを求めるアルゴリズムとしてDreyfus-Wagner法というものがあるらしいです。しかしこの方法はとても計算量が多いです。 今回紹介するプリム法ベースのシュタイナー木は、計算量は少なくて済みますがコストが最小になるとは限りません。ヒューリスティックコンテストにおける焼きなましの最中など、厳密さより速度が優先されるようなケースでの使用を想定していま
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 2021年3月から毎日問題が公開されている「競プロ典型90問」、皆さま解いていらっしゃいますでしょうか？ 一昨日、第40問として公開された「Get More Money」が解説を読み、その後いろいろな記事を見ても理解が難しかったので整理してみました。 当然のことながらこの問題の解法に触れますので、問題に挑戦したい方はこの記事は後からお読みいただくことをお勧めします。 AtCoder常設ジャッジ 問題画像 公式解説 何が理解できなかったのか 公式解説にもある通り、この問題はいわゆる「燃やす埋める問題」というタイプの問題です。公式解説は紙面
同僚に N個の集合のベン図 を描くスクリプト渡したらTwitter でちょっとバズったみたいなので解説を書きます。 N個の集合のベン図をかけるかという話で盛り上がってたら同僚がN個のベン図を描くスクリプトを作ってくれたので10個の集合のベン図貼っときますね． pic.twitter.com/ItoJQE45BT— しえら@１日目東キ17a (@sierrarries) 2017年12月19日 本解説では、Nベン図の構成方法と、本当にベン図になっていることの証明の流れを解説したいと思います。 また、上記ツイートのソースコードはここ↓に置いておきます。 github.com ブログも年1回くらいは更新しないとね。 ベン図 ベン図とは、みなさんご存知の、丸(閉曲線)の重なりから集合の部分集合や共通部分を説明するための図です。 ここでは、ベン図を以下のように定義します。 定義: ベン図 平面 上の
Le Algorithm: 高速な全点対最短経路アルゴリズム
理論計算機科学 (Thoerotical Computer Science) の色んな定理やアルゴリズムを紹介していきます. 基本的には日本語の資料がほとんどないような知見を解説していきます. 1. 全点対最短経路問題の計算量の外観 グラフ $G$ が与えられたときに全点対最短経路(APSP : all pair shortest paths)を求めたいときがあります. そんなときはほとんどの人がワーシャル・フロイド法または各点ダイクストラなどを使うかと思います. しかしこれらのアルゴリズムは頂点数 $n$ に対して最悪 $O(n^3)$ 時間かかってしまうので, $n=1000$くらいでもちょっと厳しい感じがあります. 実は辺重み付きグラフのAPSPの計算量には多くの歴史があり、ワーシャルフロイド法以降様々なアルゴリズムが提案されてきました. しかし、任意の $\epsilon>0$ に
前書き 全点対最短経路問題 (APSP : All Pair Shortest Path) を解くアルゴリズムを 4 つ紹介します。 $V$ 頂点 $E$ 辺の非負重み有向グラフ $G$ を考えます。 負の重みがあるときは一回 Bellman-Ford か何かを使ってポテンシャルを計算すれば非負に直せると思います。 お品書き Warshall-Floyd 法 Dijkstra 法を $V$ 回 Hidden Path Algorithm SHORT Algorithm 1,2 はお馴染み。 3,4 は資料も全然ないし使われてない印象。 どちらも Dijkstra を何度も回すのは無駄が多いから使いまわせるところを使いまわそうって発想のアルゴリズム。 1,2 を押さえておけば大抵の場合 (特に競プロ(非マラソン)) は問題なくて、 3,4 は少しでもいいから高速化したいときに使う可能性がある
頂点集合が $U = \set{1,\dots,N},$ $V = \set{1,2,3}$ である完全二部グラフ $G = (U, V; E)$ を考える．以下が与えられる: 正整数 $b_1, b_2, b_3$（ただし $b_1 + b_2 + b_3 = N$），各辺 $(i, j) \in E$ の正整数重み $c_{ij}$．以下の $2$ 条件を満たすように辺部分集合 $S \subseteq E$ を選ぶとき，重みの和 $\sum_{(i, j) \in S} c_{ij}$ の最大値を求めよ: 二部グラフ $(U, V; S)$ において各頂点 $i \in U$ の次数は $1$，二部グラフ $(U, V; S)$ において各頂点 $j \in V$ の次数は $b_j$． 入力に対する制約$3 \leq N \leq 10^5$$1 \leq c_{ij} \leq
概要 清一色のシャンテン数は01BFSで計算できる。 機械的な計算なので、正当性が簡単に証明できる。 シャンテン数とは テンパイするまでに必要な牌の最小枚数のこと。 例えば 🀉🀊🀍🀎🀑🀒🀙🀚🀛🀜🀜🀀🀁 のとき、🀈🀌 を引いて🀀🀁を捨てればテンパイとなる。これより少ない枚数の入れ替えでテンパイすることはできないので、この手牌のシャンテン数は2となる。 この例のようにシャンテン数がわかりやすいケースがほとんどだが、清一色のような場合はシャンテン数を求めにくい。 特にプログラムでシャンテン数を計算する場合、正しいコードを書くことは難しい。また、正当性を保証するのも難しい。 考える問題 清一色だけを考える。以下では萬子🀇🀈🀉🀊🀋🀌🀍🀎🀏だけを扱う。 複数色ある場合や字牌を含む場合でも、清一色のシャンテン数さえ計算できていれば、軽いdpで解くことが
ネットワークフロー好き好きマンとして，フローを布教したくなったので記事を書きました． ただし，フローの解説資料は既に素晴らしいものがたくさんあるので，今回は今まであまり焦点が当てられてこなかった部分を推して話をしたいと思います． テーマは，数あるフローの問題の関係を整理することです． フローの問題たちには共通の歴史があり，共通の定式化があり，共通のアルゴリズムの思想があります． その「共通」の部分を理解することで，フローに対する理解が深まり，より面白いと感じられると僕は思っていて，そこについて書きます． かなり基本的な内容しか書いてないので，強い人が得るものはあまりないかもしれません． あとこの記事はおきもちを書いてる部分が多いです． また，この記事では問題の話だけをしてアルゴリズムの詳細の話をほとんどしません．この辺りは 保坂さんのスライド などが非常に分かりやすいので，そちらを参照して
ローマと道に関するいくつかの問題とその解決 「すべての道はローマに通ず」は何を意味するのか？ 「すべての道はローマに通ず」についての問題提起と解決の提案Read less
完全に理解しても今ではもう捻くれた応用問題しか出ないので 今後解けるとは言っていないです。 数弱なのでガバってると思うけど雰囲気で察してください。 参考資料 書き終えてから見つけたけど、この記事の内容大体ここに書いてあった気がする。 再発明万歳... Graph cut optimization - Wikipedia Quadratic pseudo-Boolean optimization - Wikipedia 燃やす埋めるをグラフ表現可能な劣モジュラ関数の視点から見たもの。 これがなかったらソルバなんて作らなかった 燃やす埋める問題と劣モジュラ関数のグラフ表現可能性 その① 燃やす埋める問題と劣モジュラ関数のグラフ表現可能性 その② グラフ構築編 燃やす埋めるが出題される度に見に行くいつものやつ 最小カットを使って「燃やす埋める問題」を解く 最小カットを使って「燃やす埋める」問題を
要約 最小費用流問題に対する最短路反復法(Successive Shortest Path, SSP)や Primal-Dual 法1と呼ばれるアルゴリズムは, 少し弄ると弱多項式時間アルゴリズムにできる. 具体的には, $O(\U \cdot \mathrm{SP_+}(n, m, nC))$ が $O(m \log \U \cdot \mathrm{SP_+}(n, m, nC))$ になる. $\mathrm{SP_+}(n, m, nC)$ は$n$ 頂点 $m$ 辺, 費用高々 $nC$ のグラフの一点から全点への最短路問題を解くのにかかる時間. 以下では実装をサボったダイクストラ法なので $O(m \log m)$ だが, $\exists k: m = O(n^k)$ を仮定すると合計 $O(m^2 \log \U \log n)$. まえがき ぼくの考えたさいきょうのフロー
この記事は、Merpay Tech Openness Month 2020 の17日目の記事です。こんにちは。メルペイのMachine Learningチームのhmjです。 検知精度とオペレーション負荷のトレードオフ解消 取引の連続性に着目した検知 と不正決済の検知への機械学習の適用の内容にて投稿してきました．今回は「集団的な不正の検知」がテーマとなります． 昨今，Web不正検知やセキュリティに関わるでもECサイトでの集団による不正の手口は多様化や複雑化してきていることが報告されています[1]． メルペイでも，今後起こり得る集団的な不正決済への対策を講じる必要があると考えています． 集団的な不正は検知できたとしてもその全体像がみえにくいこともあり，ソリューションとしては「検知できること」と「すばやく全体像を把握できる」を満たすものが求められています． 両者を満たす解決方法として，グラフ理論
恥ずかしながら、最小費用流をかなりブラックボックスとして利用していたのだが、今まであまり気付いてなかったことたちが少し整理できたので雑なメモを残しておきます。アルゴリズム自体は各種資料を見てください(怠惰) 双対 LP との関係も知る人ぞ知るジャンルではあるのですが詳しい資料がたくさんあるのでそちらへ 最小費用流のライブラリを整備したい人は、これが今まで見た中で最も一般的な形をしている(fが負って何？)ので頑張って通すと良さそう。 Minimum cost b-flow フローについて詳しいことが知りたい人には Mi_Sawa さんの記事たちがかなり参考になり、今回はこれを参考にしました ぼくの考えたさいきょうのフローライブラリ - みさわめも みなさん大好き組合せ最適化も参考にしました。hosさんやwataさんやtokoharuさんの資料も有名です。 b-flow というのは、各頂点に需
要約 "最小費用流" のライブラリを "最小費用最大流" ではなく "最小費用 $\vecb$-フロー" の形で書くことについて. 「さいきょう」であって「さいそく」ではない. よくある実装に少し手を加えることで, 入力として扱える問題の範囲を広くでき, ライブラリ使用毎にアドホック気味に書く部分を減らせる. イントロ 最小費用流問題と呼ばれる問題を解く際, 競技プログラミングでは, 蟻本 に記載のものをはじめ多くの場合, 最小費用最大流を解くライブラリ, 特に最短路反復法や Primal-Dual 法 1 と呼ばれる実装が用いられる. これらのアルゴリズムを使う際, 辺コストが負になりうる場合, 負サイクルがある場合, 最小流量制約がある場合, 頂点吸込みや湧出しがある場合などは, Bellman-Ford 法や SPFA 等で追加処理を行ったり, ネットワークの変形をすることで, 同値
理解にかなり手間取った&面白かったのでメモ。 アルゴリズム やっていることは、「長さが短い順に増加路を使っていく」というだけ。 以下、頂点数 、辺数 、始点 、終点 のネットワークを考える。 残余グラフを構築しておく。 増加路がなくなるまで、以下を繰り返す。この一回の繰り返しを「1ステップ」とする。 BFSで、「容量正の辺のみを使った時の、 から までの最短路長」 を求める。 長さ の増加路がなくなるまで、DFSで増加路を選び、フローを増やす。 なる辺 以外はないものとして扱えば、増加路は全て長さ になる。 DFSの際には、「その辺を使ったフローがこれ以上流せない」状態になった辺を記録し、以降の探索では無視するようにする。つまり、その辺を使おうとしたが、 に辿り着けなかった時と、容量が0になった時、辺は死ぬ。 なお、辺が死んでも1回のステップが終わったら復活する。 計算量(一般のグラフの場
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 基本的アルゴリズム（幅優先探索など）から応用（経路復元、拡張ダイクストラなど）まで、最短経路問題に関するアルゴリズムを総特集しました。 基本的なグラフ理論の用語については、次を参考にしてください。 グラフ理論 用語集 queueなどのデータ構造の用語については、次のスライドの後半を参考にしてください。 C++ STL講習会 by @e869120 最短経路問題とは 一般的に、次のような問題とされます。 $V$ 頂点と $E$ 辺からなるグラフが与えられる。頂点 $u$ と 頂点 $v$ を結ぶパスのうち、重みの総和が最も小さいものはどれ
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
