巨大なグラフの最大重みマッチングを求める問題である． マッチングに関する一般論から，次の貪欲法を行えばよい．

• 頂点集合 \(s\) を保持する．価値の高い頂点から一つずつ見ていく．頂点 \(v\) を見るときは，\(s\) に \(v\) を追加できるならば追加する． 追加できるかどうかは，\(s\) に含まれる頂点をすべてカバーするようなマッチングが存在するか否か，で判定する．

グラフのサイズが大きいので判定を効率化していく．

\(V_i > L/2\) を満たす \(i\) についてまず考える．

二部マッチングの問題になっている． 便宜上，\(V_i \leq L/2\) ならばそれを小さい宝石，\(V_i > L/2\) ならばそれを大きい宝石と呼ぶことにする． また，大きい宝石については \(W_i=L-V_i\) とおくことにする． \(C_i \neq C_j\) かつ \(V_i \leq W_j\) なら \((i,j)\) がマッチングできるという条件になる．

マッチングの存在判定は mincut の形で考えるとわかりやすくなる．

\(V_i,W_j\) をソートして値の小さい方から見ていくことで，最大マッチングのサイズ，及びそれに使う頂点集合を見つけることができる．

まずマッチングのサイズの見つけ方について説明する． mincut の形に注目すると，適当な色 \(c\) と価値の区間 \([l,r)\) があって，

• \([0,l)\) ではすべての小さい宝石を cut する．
• \([l,r)\) では色が \(c\) でないすべての宝石を cut する．
• \([r,-)\) ではすべての大きい宝石を cut する．

という形で表せるはずである． 各色 \(c\) ごとに，\(c\) が関わる cut の最小を求めてやれば全体の最小 cut も求まる． また，上にも書いたとおり，この計算は \(V_i,W_j\) の小さい宝石から順に処理していくことでできる． この仮定で，宝石のすべての prefix について最大マッチングが求まる． \(W_j\) を追加したタイミングで最大マッチングが増大したなら，その \(W_j\) を元問題の最適解に用いてよいことがわかる． これは最初に説明した貪欲法を行うことと同値になる．

こうして，\(V_i>L/2\) を満たす宝石すべてについて，それを最終的に使うか否かが定まった． 以後，使わないとわかった宝石はすべてないものとして考える． つまり，大きい宝石と言った場合には，それを必ず使うこととする．

続いて小さい宝石をどう使うか考える． 小さい宝石の個数を \(A\)，大きい宝石の個数を \(B\) とおく．

小さい宝石と大きい宝石とのマッチングにはいくらかの自由度がある． 各色 \(c\) について，大きい宝石とのマッチングに使わない小さい色 \(c\) の宝石の個数が重要になる． この個数の最小値を \(f(c)\) とおくことにする． \(f(c)\) 自体は簡単に求まる． 色 \(c\) の小さい宝石と大きい宝石だけでマッチングを作って，使わなかった個数が \(f(c)\) である． （ここに色 \(c\) 以外の小さい宝石を足したあと，適切にマッチングを組み替えることで，色 \(c\) を使う個数を変えずに，すべての大きい宝石をマッチさせることができる．）

\(2f(c)>A-B\) となる色 \(c\) が存在する場合としない場合に分けて考える．

\(2f(c)>A-B\) となる色 \(c\) が存在する場合：

明らかに色 \(c\) が余り，\(2f(c)-(A-B)\) 個消す必要がある． 逆にこれだけ消せば十分であることがあとの議論を追うことでわかる． \(f(c)\) の値が減るような色\(c\) の宝石を価値の小さい順に\(2f(c)-(A-B)\) 個消すことで，最適解が得られる． \(f(c)\) の値の計算方法を考えると，色 \(c\) の小さい宝石を \(+1\), 色 \(c\) 以外の大きい宝石を \(-1\) に対応させてできる累積和が重要だとわかる． この累積和の min が変化しないように色 \(c\) の小さい宝石を消せばよい．

\(2f(c)>A-B\) となる色 \(c\) が存在しない場合：

\((A-B)\) が偶数のとき，完全マッチングが存在する． まず大きい宝石をすべて使うマッチングを適当に構成する． ここで，\((A-B)\) 個の小さい宝石が残る． ここで過半数を占めるような色 \(c\) がなければ嬉しい． そのような色 \(c\) があったとする． ところで，\(f(c) \leq (A-B)/2\) であった． この \(f(c)\) を達成するようなマッチングとの XOR をとり，交互路でマッチングを入れ替えることを繰り返していく． するとちょうど色 \(c\) の余りの個数が \((A-B)/2\) になるタイミングがあり，ここで余った宝石たちをすべてマッチングさせることができる．

\((A-B)\) が奇数のとき： \(1\) 頂点削る必要がある．そして \(1\) 頂点削るのが十分． 大きい宝石とのマッチングを破壊しない範囲で，最も価値の小さい宝石を消せば良い． これは，小さい宝石と大きい宝石のマッチングを求める操作を \(V_i,W_i\) の大きい順に行えばよい． こうすると，小さい宝石の中でできるだけ価値の大きいものを使うようなマッチングが得られる．このマッチングに使われなかった宝石のうち，最も価値の小さい宝石を消せばよい．

ソート以外は線形時間でできる． 全体で \(O(N \log N)\) 時間の解法が得られた．

実装例