「ネタ」の記事一覧

二部グラフの最大マッチング、最小点被覆、最大安定集合、最小辺被覆は相互のあいだに密接な関係があります。 グラフ上の最適化問題として有名なものとして、最大マッチング問題、最小点被覆問題、最大安定集合問題、最小辺被覆問題があ・・・

続きを読む

AtCoder NoviStepsを埋めてみる(30) 最大流・最小カット問題 1D 2Dの続きです。今回は燃やす埋める問題です。 燃やす埋める問題とは？ 燃やす埋める問題とは以下のような問題です。 N 個のゴミがある。・・・

続きを読む

AtCoder NoviStepsを埋めてみる(30) 二重辺連結成分分解の続きです。今回は最大流問題です。 最大流問題は、容量制限付きネットワークで源点から終点へ流せる量の最大値を求める問題です。配送・通信・割当てなど・・・

続きを読む

第3回 岩井星人アンソロジープログラミングコンテストが開催されていたので参加しました。結果は全 8 問のうち 4 問正解。118 人中 81 位という残念な結果になりました。 岩井星人さんはどんな人？ おもに AtCod・・・

続きを読む

AtCoder NoviStepsを埋めてみる(29) サイクル検出の続きです。今回は二重辺連結成分分解です。 二重辺連結成分分解とは？ 無向グラフで、2 つの頂点（u, v）の間にどの 1 本の辺を取り除いても両者は連・・・

続きを読む

AtCoder NoviStepsを埋めてみる(28) 幅優先探索 1Dの続きです。今回はサイクル検出です。 C – Find it! C – Find it! 問題の概要 N 頂点 N 辺の有向・・・

続きを読む

AtCoder NoviStepsを埋めてみる(26) 幅優先探索 1Qの続きです。今回も幅優先探索（BFS）です。やや難しめの問題に挑戦します。 E – Transitivity E – Tra・・・

続きを読む

AtCoder NoviStepsを埋めてみる(26) 幅優先探索 2Qの続きです。今回も幅優先探索（BFS）です。やや難しめの問題に挑戦します。 D – Reachability Query 2 D ・・・

続きを読む

AtCoder NoviStepsを埋めてみる(25) 幅優先探索 3Q 基本問題の続きです。今回も幅優先探索（BFS）です。 C – Tour C – Tour 問題の概要 N 個の頂点とM 個・・・

続きを読む

AtCoder NoviStepsを埋めてみる(24) スタック：かっこ列を扱うの続きです。今回は幅優先探索（BFS）です。 幅優先探索は、スタートから近い頂点から順に探索していくアルゴリズムです。辺の重みが同じグラフで・・・

続きを読む