燃やす埋める問題とProject Selection Problemの整理 - Qiita
2021年3月から毎日問題が公開されている「競プロ典型90問」、皆さま解いていらっしゃいますでしょうか？ 一昨日、第40問として公開された「Get More Money」が解説を読み、その後いろいろな記事を見ても理解が難しかったので整理してみました。 当然のことながらこの問題の解法に触れますので、問題に挑戦したい方はこの記事は後からお読みいただくことをお勧めします。 AtCoder常設ジャッジ 問題画像 公式解説 何が理解できなかったのか 公式解説にもある通り、この問題はいわゆる「燃やす埋める問題」というタイプの問題です。公式解説は紙面の都合もあって要点を絞って書かれているので、ほとんど予備知識がなかった筆者の場合はあまり腹落ちしませんでした。そこで「燃やす埋める問題」というキーワードを元にググってみて記事を色々と読んだのですが、どうもこの問題を解くやり方はいくつかパターンがあるようで、書
N個の集合のベン図が描けること - ぬぬろぐ
同僚に N個の集合のベン図 を描くスクリプト渡したらTwitter でちょっとバズったみたいなので解説を書きます。 N個の集合のベン図をかけるかという話で盛り上がってたら同僚がN個のベン図を描くスクリプトを作ってくれたので10個の集合のベン図貼っときますね． pic.twitter.com/ItoJQE45BT— しえら@１日目東キ17a (@sierrarries) 2017年12月19日 本解説では、Nベン図の構成方法と、本当にベン図になっていることの証明の流れを解説したいと思います。 また、上記ツイートのソースコードはここ↓に置いておきます。 github.com ブログも年1回くらいは更新しないとね。 ベン図 ベン図とは、みなさんご存知の、丸(閉曲線)の重なりから集合の部分集合や共通部分を説明するための図です。 ここでは、ベン図を以下のように定義します。 定義: ベン図 平面 上の
AGC018: C – Coins を離散凸解析（L 凸関数最小化）で解く
頂点集合が $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で計算する - yukinote
概要 清一色のシャンテン数は01BFSで計算できる。 機械的な計算なので、正当性が簡単に証明できる。 シャンテン数とは テンパイするまでに必要な牌の最小枚数のこと。 例えば 🀉🀊🀍🀎🀑🀒🀙🀚🀛🀜🀜🀀🀁 のとき、🀈🀌 を引いて🀀🀁を捨てればテンパイとなる。これより少ない枚数の入れ替えでテンパイすることはできないので、この手牌のシャンテン数は2となる。 この例のようにシャンテン数がわかりやすいケースがほとんどだが、清一色のような場合はシャンテン数を求めにくい。 特にプログラムでシャンテン数を計算する場合、正しいコードを書くことは難しい。また、正当性を保証するのも難しい。 考える問題 清一色だけを考える。以下では萬子🀇🀈🀉🀊🀋🀌🀍🀎🀏だけを扱う。 複数色ある場合や字牌を含む場合でも、清一色のシャンテン数さえ計算できていれば、軽いdpで解くことが
ネットワークフロー問題たちの関係を俯瞰する - 私と理論
ネットワークフロー好き好きマンとして，フローを布教したくなったので記事を書きました． ただし，フローの解説資料は既に素晴らしいものがたくさんあるので，今回は今まであまり焦点が当てられてこなかった部分を推して話をしたいと思います． テーマは，数あるフローの問題の関係を整理することです． フローの問題たちには共通の歴史があり，共通の定式化があり，共通のアルゴリズムの思想があります． その「共通」の部分を理解することで，フローに対する理解が深まり，より面白いと感じられると僕は思っていて，そこについて書きます． かなり基本的な内容しか書いてないので，強い人が得るものはあまりないかもしれません． あとこの記事はおきもちを書いてる部分が多いです． また，この記事では問題の話だけをしてアルゴリズムの詳細の話をほとんどしません．この辺りは 保坂さんのスライド などが非常に分かりやすいので，そちらを参照して
ローマと道に関するいくつかの問題とその解決
ローマと道に関するいくつかの問題とその解決 「すべての道はローマに通ず」は何を意味するのか？ 「すべての道はローマに通ず」についての問題提起と解決の提案Read less
燃やす埋める問題を完全に理解した話 - koyumeishiのブログ
完全に理解しても今ではもう捻くれた応用問題しか出ないので 今後解けるとは言っていないです。 数弱なのでガバってると思うけど雰囲気で察してください。 参考資料 書き終えてから見つけたけど、この記事の内容大体ここに書いてあった気がする。 再発明万歳... 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]． メルペイでも，今後起こり得る集団的な不正決済への対策を講じる必要があると考えています． 集団的な不正は検知できたとしてもその全体像がみえにくいこともあり，ソリューションとしては「検知できること」と「すばやく全体像を把握できる」を満たすものが求められています． 両者を満たす解決方法として，グラフ理論
最小費用流についてのちょっとしたメモ - gdgdiary
恥ずかしながら、最小費用流をかなりブラックボックスとして利用していたのだが、今まであまり気付いてなかったことたちが少し整理できたので雑なメモを残しておきます。アルゴリズム自体は各種資料を見てください(怠惰) 双対 LP との関係も知る人ぞ知るジャンルではあるのですが詳しい資料がたくさんあるのでそちらへ 最小費用流のライブラリを整備したい人は、これが今まで見た中で最も一般的な形をしている(fが負って何？)ので頑張って通すと良さそう。 Minimum cost b-flow フローについて詳しいことが知りたい人には Mi_Sawa さんの記事たちがかなり参考になり、今回はこれを参考にしました ぼくの考えたさいきょうのフローライブラリ - みさわめも みなさん大好き組合せ最適化も参考にしました。hosさんやwataさんやtokoharuさんの資料も有名です。 b-flow というのは、各頂点に需
ぼくの考えたさいきょうのフローライブラリ
要約 "最小費用流" のライブラリを "最小費用最大流" ではなく "最小費用 $\vecb$-フロー" の形で書くことについて. 「さいきょう」であって「さいそく」ではない. よくある実装に少し手を加えることで, 入力として扱える問題の範囲を広くでき, ライブラリ使用毎にアドホック気味に書く部分を減らせる. イントロ 最小費用流問題と呼ばれる問題を解く際, 競技プログラミングでは, 蟻本 に記載のものをはじめ多くの場合, 最小費用最大流を解くライブラリ, 特に最短路反復法や Primal-Dual 法 1 と呼ばれる実装が用いられる. これらのアルゴリズムを使う際, 辺コストが負になりうる場合, 負サイクルがある場合, 最小流量制約がある場合, 頂点吸込みや湧出しがある場合などは, Bellman-Ford 法や SPFA 等で追加処理を行ったり, ネットワークの変形をすることで, 同値
Dinic法について - TAISA_'s blog
理解にかなり手間取った&面白かったのでメモ。 アルゴリズム やっていることは、「長さが短い順に増加路を使っていく」というだけ。 以下、頂点数 、辺数 、始点 、終点 のネットワークを考える。 残余グラフを構築しておく。 増加路がなくなるまで、以下を繰り返す。この一回の繰り返しを「1ステップ」とする。 BFSで、「容量正の辺のみを使った時の、 から までの最短路長」 を求める。 長さ の増加路がなくなるまで、DFSで増加路を選び、フローを増やす。 なる辺 以外はないものとして扱えば、増加路は全て長さ になる。 DFSの際には、「その辺を使ったフローがこれ以上流せない」状態になった辺を記録し、以降の探索では無視するようにする。つまり、その辺を使おうとしたが、 に辿り着けなかった時と、容量が0になった時、辺は死ぬ。 なお、辺が死んでも1回のステップが終わったら復活する。 計算量(一般のグラフの場
最短経路問題総特集！！！～BFSから拡張ダイクストラまで～ - Qiita
基本的アルゴリズム（幅優先探索など）から応用（経路復元、拡張ダイクストラなど）まで、最短経路問題に関するアルゴリズムを総特集しました。 基本的なグラフ理論の用語については、次を参考にしてください。 グラフ理論 用語集 queueなどのデータ構造の用語については、次のスライドの後半を参考にしてください。 C++ STL講習会 by @e869120 最短経路問題とは 一般的に、次のような問題とされます。 $V$ 頂点と $E$ 辺からなるグラフが与えられる。頂点 $u$ と 頂点 $v$ を結ぶパスのうち、重みの総和が最も小さいものはどれか。 始点を固定して他のすべての頂点との対について最短経路問題を解く場合や、任意の2頂点の対について解く場合などが実際には多いです。 実社会とも強く密着した問題のため、古くからたくさん効率的な解法が考えられてきました。 今回はそれらを紹介しつつ、細かいテクニ
行列木定理の証明 - blogoid
0. はじめに 今回は行列木定理(Kirchhoff's theorem)の証明を紹介してみようと思います。 行列木定理とは、全域木の個数の数え上げに関する定理です。証明方法はいくつかありますが、今回は漸化式を用いた全域木の個数の数え上げとの対応を見ることで定理を証明してみたいと思います。 1. 定理の内容 頂点数$n$のループを含まない多重無向グラフ$G$が与えられたとします。対角成分に頂点の次数を並べた行列から、隣接行列*1を引いたものをラプラシアン行列といいます。つまり、$G$に対する$n$×$n$ラプラシアン行列$L=(l_{ij})$は$$\begin{aligned}l_{ij}=\begin{cases}\text{頂点iの次数}&(i=j)\\ \text{頂点iと頂点jの間の辺の数}\times (-1)&(\mathrm{otherwise}) \end{cases}
トポロジカルソートと強連結成分分解でWikipediaの特定カテゴリー配下のページをすべて取得する - 終末 A.I.
Wikipediaの特定カテゴリー配下のページをすべて取得するためには、整理されていないグラフデータ特有のいくつかの問題に向き合う必要があります。 一つは、Category:カツラ科と糸井の大カツラのように、サブカテゴリーにはページへのリンクが含まれているが、カテゴリー本体にはページへのリンクが含まれていないケースがあるという問題。 もう一つは、Category:インフォグラム・エンターテインメントームソフトとCategory:アタリのゲームソフトのように、お互いがお互いのサブカテゴリーに含まれてしまっているケースがあるという問題です。 これらの問題は、以下の手順を踏むことで解決できます。 カテゴリーにリンクされているページだけでなく、サブカテゴリー内のリンクを順にたどって含まれるすべてのページを収集する ただし、一度たどったカテゴリーに再度到達した場合、それ以上はそのルートを探索しない
Graph Golf参加記
理論計算機科学 (Thoerotical Computer Science) の色んな定理やアルゴリズムを紹介していきます. 基本的には日本語の資料がほとんどないような知見を解説していきます. NII主催のグラフコンペティション Graph Golfに助教とM2の先輩と僕の3人チームで参加して優勝し、12/10に札幌で開かれたCANDAR'15にて講演をしました。(めっちゃ高そうな盾とかもらいました！！！)ということでGraph Golfの問題内容や背景、および僕らのとった手法の概略について適当に書いていきます。 前提知識として知っておいてほしい単語は以下の2つくらいです。 グラフ(点と点が繋がってるアレのこと) 次数(頂点に繋がってる辺の本数のこと) 問題内容 自然数nとdが与えられる。頂点数nでどの頂点の次数もd以下であるようなグラフのうち 1. 直径 2. ASPL が小さいものを構
最短経路の個数も一緒に数え上げる最短経路アルゴリズム - けんちょんの競プロ精進記録
ARC 090 E - Avoiding Collision で話題になったこともあり、簡単にメモします。 最短経路を求める DP 的処理をするとき、DAG上のDP だろうと、BFS だろうと、Dijkstra だろうと、以下のような緩和処理をやっています // Edge e の緩和 int dp[MAX_V]; // dp[v] := 始点 s から頂点 v への最短経路長 if (dp[e.to] < dp[e.from] + e.cost) { dp[e.to] = dp[e.from] + e.cost; } これをちょっと変えるだけで、最短経路の本数も一緒に数え上げられます。 // Edge e の緩和 int dp[MAX_V]; // dp[v] := 始点 s から頂点 v への最短経路長 int num[MAX_V]; // num[v] := 始点 s から頂点
実世界で超頻出！二部マッチング (輸送問題、ネットワークフロー問題）の解法を総整理！ - Qiita
0. はじめに --- 二部マッチング問題は実世界で超頻出 はじめまして。NTTデータ数理システムでアルゴリズムを探求している大槻 (通称、けんちょん) です。 好きなアルゴリズムはタイトルにもある二部マッチングですが、会社ではなぜか「DP が好きな人」と呼ばれています。 以前に動的計画法 (DP) の典型パターンを整理した記事を執筆したのですが、DP と並んで超頻出の話題として二部マッチング問題があります。二部マッチング問題とは、例えばマッチングアプリなどに見られるように、2 つのカテゴリ間で最適なマッチングを構成していく問題です。実問題で登場する二部マッチングは以下のように多岐にわたります: マッチングアプリで男女のペアを最適化する (「男」と「女」) インターネット広告分野で、ユーザの興味に合う広告を出す (「ユーザ」と「広告」) 企業検索サービスなどで、ユーザの検索履歴に合う企業を
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
cakes（ケイクス）
サンタコンペで二度全完した話
