燃やす埋める問題の解説記事です

燃やす埋める(Project Selection Problem)の練習問題についての解説です。問題はこちら ポイント 問題概要 解説 提出プログラム 感想 ポイント 負のコスト 複数の選択肢 機械的なグラフの構築 問題概要人の人が数直線上に家を建てようとしています。番目の人…

燃やす埋める(Project Selection Problem)の練習問題についての解説です。問題はこちら ポイント 問題概要 解説 提出プログラム 感想 ポイント 最大化を最小化へ言い換える グラフ表現可能なコストの性質 2部グラフの性質を用いたの選択肢の順序変更 問題概…

燃やす埋める(Project Selection Problem)の練習問題についての解説です。問題はこちら ポイント 問題概要 解説 提出プログラム 感想 ポイント 選択に対するコストからグラフを構築する 問題概要からなる文字列が与えられます。円支払うことにより、を(なら…

問題はこちら 問題概要 解説 例 提出プログラム 感想 問題概要頂点のグラフがあり，頂点から頂点に重みの有向辺が張られている．頂点から頂点までの最短距離を求めよ．解説であるからは なら なら となります．頂点をでソートすると，各についてとなるやとな…

メモがてら書きます．問題はこちら 問題概要 解説 提出プログラム 感想 問題概要長さの数列を作る．各には個の選択肢があり，を選ぶとのコストがかかる．さらに，各についてのコストが追加でかかる．コストの総和の最小値を求めよ．解説複数の選択間にコスト…

公式解説より効率の良いアルゴリズムの説明です．問題はこちら 問題概要 解説 関連問題 問題概要頂点辺の有向グラフが与えられる．各について，辺のみ通れないときの頂点から頂点までの最短距離を求めよ．解説頂点から頂点までの最短経路を一つ求めます．明…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要個のボールがあり，各ボールにはから以下の整数が書かれたボールはちょうど2個ずつ存在する．本の筒があり，各筒にはボールが個入っている．異なる本の筒の一番上にあるボールの色が同じ場合それら…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要頂点辺の有向グラフがあり，人が人ずつ頂点から辺を辿って任意の回数繰り返す．人が人以上通った頂点のの値の総和の最大値を求めよ．解説ある強連結成分を通るときはその強連結成分の全頂点を通るべ…

公式解説とは別の解法です． 問題はこちら 問題概要 解説1：最大二部マッチング 解説2：2-SAT 提出プログラム 感想 問題概要と番号付けされた個の白い球がある．球または球を選んで黒く塗ることができるという操作を回行う．すべての球を黒で塗ることが可能…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要頂点の完全無向グラフから辺取り除く．このグラフの頂点から本の辺を辿るパス(一つの辺を複数回辿ってもいい)のうち終点が頂点であるようなパスの数を求めよ．解説頂点から頂点への長さのパス(厳密…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要最初紙に文字書いてある．コピーとペーストを行うことにより，紙に文字以上書いてあるようにしたい．コピーには，ペーストにはのコストがかかる．最小でいくらのコストがかかるか．解説連続でコピー…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要頂点の根付き木について以下の個のクエリに答えよ．整数が与えられる．次の条件を満たす頂点の個数を求めよ． から根への最短パス上に頂点が存在する． から根への最短パスに含まれる辺の数がちょう…

公式解説と同じになってしまいましたが，せっかく書いたので公開します．問題はこちら 問題概要 解説 提出プログラム 感想 問題概要頂点の木の任意の頂点についての総和を求めよ．ただし，とはからへの最短パスに含まれる辺全ての重みのXORと定める．解説も…

問題はこちら 問題概要 問題概要2 解説 別解 提出プログラム 感想 問題概要頂点辺の単純無向グラフの各頂点を赤，緑，青で塗り分ける方法で隣接する頂点が異なる色で塗られているようなものは何通りあるか．問題概要2グラフ理論っぽく書かれていますが，同じ…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要頂点辺の連結無向グラフの各辺に英小文字がつ書かれている．頂点から頂点までのウォークのうち，通った辺に書かれた文字を順に並べると回文となるようなものの回文の長さの最小値を求めよ．解説 回…

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要のマス目が白か黒に塗られており，塗られていないマスもある．塗られていないマスを白か黒で塗るとき，隣り合ったマスが異なる色で塗られているようなマスの組の数の最大値を求めよ．解説 隣り合っ…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要頂点の重み無し有向グラフの隣接行列が与えられる．任意の頂点から任意の頂点までちょうど本の辺を辿って行くことのができるか判定せよ．思考の流れ yukicoder No.1340 おーじ君をさがせとほ…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要ラベル付き頂点のパスグラフから頂点を削除していく. 頂点をつ削除するたび連結成分の個数の点数を得る. 通りの削除の仕方すべての点数の総和を求めよ.思考の流れ 連結成分の数というのは数え…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要頂点辺の有向グラフの頂点からちょうど本の辺を辿って行くことのできる頂点の個数を求めよ.思考の流れ yukicoder No.1112 冥界の音楽の解法で書いたように隣接行列を乗した行列の成分は「頂点…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要頂点の有向グラフが与えられる. グラフが空になるまで以下の操作を繰り返す. 残っている頂点のうちランダムに一つを選び, その頂点およびその頂点から辺をたどって到達できる頂点を削除する. …

問題はこちら 問題概要 解説 提出プログラム 感想 問題概要行列のマスのうちいくつかを選ぶ. 行列のマスを選ぶと, 円失う. また, 行目のすべてのマスを選ぶと円得ることができ, 列目のすべてのマスを選ぶと円得ることができる. このとき最大何円得ることがで…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要 頂点の木が与えられる. に対してが以下のように定義される時, を求めよ. 以上以下の頂点からなる誘導部分グラフの連結成分数 思考の流れ 式通り素直にしようとしても間に合わない. となるの…

問題はこちら 問題概要 思考の流れ 01-BFSとは 提出プログラム 感想 問題概要 全長の道路の途中に個の安全島がある. 各安全島はの位置にあり, 位置がである安全島と位置がである安全島があることは保証される. 青信号の時間が, 赤信号の時間がであり, 人が移…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要 頂点の木と, 各頂点にの値が与えられる. 全ての頂点に対して, 頂点1から頂点までのパスを頂点1から見た数列ととらえて狭義最長増加部分列の長さを求めよ. 思考の流れ ある数列Sが与えられた…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要 頂点辺の閉路のない有向グラフ(=DAG)が与えられる. 頂点から辺をたどって頂点Nに行くことを考える. 各頂点から出ている辺から等確率でランダムに選び進む. このグラフから一つだけ辺を取り除…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要 個の都市からなる辺の連結グラフが与えられる. また, 各頂点について枚の銀貨を得るために必要な時間, 各辺について移動にかかる銀貨枚と時間が与えられる. 都市1から各都市に行くために必要…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要 2次元上の点が与えらえれる. すべての点集合について, その集合のすべての点を含む最小の長方形の内部にある点の総数を998244353で割った値を求めよ. 思考の流れ 全列挙できない場合は寄与分…

問題はこちら 問題概要 思考の流れ(自分の解法) 思考の流れ(公式解説動画の解法) 思考の流れ(公式解説pdfの解法) 提出プログラム 感想 問題概要 東西に無限に続く1本の大通りがあり, 数直線とみなすことができる. 回道路工事が行われる. 番目の道路工事は時…

問題はこちら 問題概要 思考の流れ 提出プログラム 感想 問題概要 頂点の木が与えられる. 木の各辺には色が塗られていて長さはである. このとき, 以下の個の問いに答えよ. 色が塗られている辺の長さがに変更されたと仮定したときの二頂点間の距離を求めよ. (…