問題（外部リンク） 2395 -- Out of Hay 実装の概要 最終的に構成したいのは最小全域木ですが、今回は距離の総和ではなく全域木を構成する辺の中で最長のものの長さです。 そのため、クラスカル法の一部を変更し最大の距離を保存できるようにすることで解く…

問題（外部リンク） 2377 -- Bad Cowtractors 実装の概要 今回は普段とは異なり「なるべくコストの大きい」全域木を作ることが目標です。 ただ、既にプリム法やクラスカル法を実装したことがあれば条件式を逆にすれば良いので既存のコードを再利用することが…

問題（外部リンク） 1258 -- Agri-Net 実装の概要 グラフ全体での最小コストを求める問題です。今回の実装ではクラスカル法を使いました。 クラスカル法の計算量は頂点数をE, 辺の数をVとするとです。今回は密グラフなので辺の数はそれなりに多いですが十分…

問題（外部リンク） 3268 -- Silver Cow Party 実装の概要 （2/20 下部に追記あり） パーティー会場xまでの往復距離の最大値を求めたいので、それぞれの地点からxまでの最短距離と、xからそれぞれの地点までの最短距離を求める必要があります。 Nアルゴリズ…

問題（外部リンク） 3259 -- Wormholes 実装の概要 今回の問題ではそれぞれのfieldを行き来するのにpathとwormholeを使うことができ、後者では時間を遡ることができます。 つまり、wormholeの移動コストをマイナスとして扱い、負の閉路（移動距離がマイナス…

問題（外部リンク） 2139 -- Six Degrees of Cowvin Bacon 実装の概要 aとbが共演したことがあれば距離1、aとbは共演してはいないがcはaやbと共演したことがあれば距離2、…というようにab間の距離を定義すれば全点対最短路の問題と考えることができます。 n …

問題（外部リンク） 3181 -- Dollar Dayz 実装の概要 動的計画法で解きます。 決まった合計金額における品物の買い方のパターン数を問う問題ですが、例えば合計が$5なら「$1 $1 $1 $2」のように必ず安い順に購入すると決めると考えやすくなります。そこでdp[…

問題（外部リンク） 3046 -- Ant Counting 実装の概要 動的計画法を用います。 問題にあるように{1,2}と{2,1}などを重複して数えないように気をつける必要がありますが、そのためには「数字は必ず小さい順に並べる」と考えると分かりやすくなります。そしてd…

問題（外部リンク） 3616 -- Milking Time 実装の概要 「ある時点までに採れるミルクの量」を保存しつつ動的計画法で解きます。事前にインターバルを搾乳開始時を基準にソートし、その時間になったら直前までのミルクの量と新たに採れるミルクの量を足して「…