以上の条件が成り立つ事により、以下のような二分探索ができます。105とかでも許されます。枝の重み付き無向グラフが与えられます。このグラフは連結であること、多重辺やセルフループがないことは保証されています。計算する代表的なアルゴリズムに、プリムのアルゴリズムがあります*9。Wikipedia平たく言ってしまえば、重みの軽い枝は、ループを作らない限り、片っ端から最小全域木を構成するものと考えて良い。事によって作る事ができます。全域木上の2頂点間のパス中の最大辺を求める方法というわけで、最小全域上の2頂点間のパスの最大辺を求める必要が出るんですが。1010くらいあるので無理です。ancestor)を求めるアルゴリズムを応用することで効率よく計算できます。以下のような擬似コードにより、不必要な所をすっ飛ばしながら親を見つける、というものです。以下のような擬似コードが使えるのです。計算量で解く事ができます。ancestorを解く実装もする必要があるので糞だるかったです。EF解けなかったけどGが解けた。枝の無向グラフが与えられます。重みが与えられています。得点を「Uに含まれる枝の重みの総和ーUに含まれる頂点の重みの総和」で定義します。この最大値を求めてください。何となく燃やす埋める問題っぽさがあるなぁと思いながら考えてたらグラフの最小カットに帰着できました。対応する頂点集合を持つようなグラフを考えて枝を以下のように張ります。属する点を端点に持つ全ての枝~終点の経路をカットしなければいけないですよね。後者のカットによる値が、「Uに含まれない頂点を端点にもつ枝は、そもそもの得点を得られない分」にそれぞれ対応していると捉える事ができます。よって、この減点分を最小にするのが得点を最大にする事と等価といえるのです。後は最大フローのライブラリで殴るだけですね。終わりに競プロ勢じゃない方にこの記事ってどのくらい伝わるんですかね...分かりづらかったらすみません(ぷよぷよぶり2回目)ともあれ、それなりに歯ごたえのある問題も解けたし、このあたりをサクサク解けるようなライブラリ化したいなーと言うモチベにもなったので、個人的には良い機会でした。これからも競プロやっていきます*12。*1:合宿当時まだ他の方の参戦は決まって居なかったので、4人で計算してます*2:当時の記事のdemo画面などでご確認ください*3:本質でないので脚注に書きますが、Round55のABCDGも解いてあります*4:別に階段が好きな訳ではないです*5:詭弁です。doubleできそうですが競プロで使えるか分からないので未確認*9:あとクラスカルもありますが。Wikipedia*12:でもそろそろ競プロ以外の趣味コーディングもしたいんですよね。月別アーカイブはてなブログをはじめよう!yaoshimaxさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。