Don't cut line!
実は一回目も参加していて、こんな問題:
題材としては、最近クラスカル法やプリム法の最適性の証明とかを勉強したので、このあたりに着想を得て作りました。
実は、元の問題は \( P(T) = \sum_{i \in I}p_i \) と定義されていたのですが、これのいい感じの解法がわからなかったので \( P(T) = \max_{i \in I} p_i \) として出題しました。(調査の結果、元のやつは NP-hard で、色々となんか手法の提案はみたのですがいまいちわからずでした.)
感想としては、テストケースを作るのがとても難しかったです.
問題の性質上、 \( n \) 番目の(?) 最小全域木からがコストの制約を満たす...みたいな感じにしなくてはいけない上、 そもそも入力は連結で単純にしないといけないので、脳死でランダムに作るみたいなことは当然ダメで、解法からいい感じに逆算して作る必要があったので色々と勉強になりました。
コンテスト中の提出を見ていると、この辺頑張って作ったテストケースがかなり撃墜してくれていたのでとてもよかったです。
前回のコンテストではかなり後ろの方の問題だったのでそこまで大量の提出が飛んでこなくて暇だな〜と思っていたのですが、 今回は70以上の提出があり、30人以上の方に解いていただけてとても嬉しかったです、ぜひ解いてみてください！
また、解説を頑張って書いたのでここにも掲載しておきます。
解説(ネタバレ注意)
\( P(T) \) は、 \( T \) に含まれる最も \( p_e \) の大きい辺の \( p_e \) のみによって決まります。
そのため、 条件を満たすように \( P(T) \) を最大化するには、なるべく大きい \( p_e \) を持つ辺を一つ採用し、あとはコストが最も小さくなるような全域木を作れば良いです。
つまり、
- 利益の大きい順に辺を選び、これを含むようなコストの最も小さい全域木 \( T' \) を求める
- \( W(T') \leq C \) なら選んだ辺の利益を出力して終了
- 満たさないなら次に大きい辺を選ぶ
- 最後まで満たさなかったら \( -1 \) を出力して終了
という方法で今回の問題を解くことができます。
これを行う最も素直な方法は、辺を一つ選んだのちに、その辺が結ぶ二つの頂点をまとめて新しく得たグラフの最小全域木を得て、条件を満たすか確認することです。
しかし、最小全域木を作る際には \( N-2 \) 本の辺を選ぶ必要があるので、 毎回 \( \Omega(N) \) の計算量がかかってしまいます。
そして、あらかじめ選ぶ辺の候補は \( K \) 本あるので、今回の制約でこのアルゴリズムを時間内に実行することは難しいです。
そこで、これを高速化することを考えます。
実は、毎回最小全域木を求め直すのではなく、与えられたグラフ \( G \) に対する最小全域木をあらかじめ求めておくと、
ある辺が含まれるような全域木の最小コストを高速に求めることができます。
\( G \) の最小全域木 \( T = (V, E) \) をあらかじめ求めたとします。
これに操作を加えることで、辺 \( e \notin E \) が含まれるような全域木のうち最もコストが小さくなるようなものを得たいです。
まず、 \( e \) を \( T \) に加えると、 \( T \) にあらたに閉路がただひとつできます。
したがって、この閉路の辺をどれかひとつ削除すれば全域木となります。
そしてこのとき、この閉路の辺のうち \( e \) 以外で最もコストの大きい辺を削除することで \( e \) を含む最もコストの小さい全域木を得ることができます。
これは、あらかじめ \( e \) を採用した状態でクラスカル法を適用することを考えればわかります。
この閉路を構成する辺のうち、最後に選ばれる辺である最もコストの大きい辺を追加すると、 \( e \) がすでにあることから閉路ができるため、採用されなくなるためです。
したがって、 \( e \) が含まれる最もコストの小さい全域木は、
木 \( T \) があったとき、
「 \( T \) に 辺 \( e \) を追加したとき、できる閉路の辺のうち \( e \) 以外で最もコストが高いものはいくつか？」
というクエリに高速で答えられるようになれば、高速に求まることになります。
ここからは、これについて考えます。
削除する辺の高速な求め方
ここで、できる閉路は、 \( u, v \) の最小共通祖先を \( r \) としたときに
「 \( u \) から \( r \) を繋ぐ経路と \( v \) から \( r \) を繋ぐ経路という二つの経路が合わさったものである」ということに注目します。
すると、 \( u, v \) を繋いだことでできる閉路の辺のコストの最大値は、
「 \( u \) から \( r \) への経路の最大値」 と 「 \( v \) から \( r \) への経路の最大値」 の大きい方になります。
つまり、先ほどのクエリは 「 \( T \) の \( u, v \) の最小共通祖先までの経路上のうち最もコストが高いものはいくつか？」
と言い換えられ、これにはダブリングと呼ばれるテクニックを用いると高速に答えることができます。
ダブリングを用いると、頂点数 \( V \) の木の二つの頂点 \( u, v \) の最小共通祖先は \( O(\log V) \) で求めることができます。
さらに、これを求める際に、各頂点からの親への遷移の情報と共に、親への遷移の経路上の辺のコストの最大値を管理することで、
\( u, v \) それぞれからの最小共通祖先への経路上の最大コストを同時に求められます。
したがって、この方法で \( O(\log N) \) の時間計算量で目的の辺を特定することができます。
最終的なアルゴリズム
ここまでの議論から、最初に登場した
- 利益の大きい順に辺を選び、これを含むようなコストの最も小さい全域木 \( T' \) を求める
- \( W(T') \leq C \) なら選んだ辺の利益を出力して終了
- 満たさないなら次に大きい辺を選ぶ
- 最後まで満たさなかったら \( -1 \) を出力して終了
という方法は、
クラスカル法などで、 \( O(K \log K + K \alpha(N)) \) の時間計算量であらかじめ \( G \) の最小全域木 \( T \) を求めておくことで、
\1. の時間計算量が 毎回 \( O (\log N) \) となり、
試す辺の数は高々 \( K \) 本なので、全体としては \( O(K \log K + K \log N) \) の時間計算量となります。
今回の問題では、このアルゴリズムを時間制限に十分間に合うように動作させることが可能です。
また、準備でいろいろと