Hatena::Grouptopcoder

解いた問題

TopCoder: OgieKako / Codeforces: OgieKako

 | 

2011-12-31

SRM526.5 1000

23:09

{match_i} , {red_i} , {blue_i} が与えられる. match[i], red[i], blue[i] がひとつの封筒に入っている.

封筒のサブセットをとって,以下を満たすようにする

封筒の数が最大,

そのいかなる空でない部分集合をとっても,Nim で先手が勝つ(マッチのxor が0 にならない)

赤の総和 * 青の総和 が最小

赤の総和 * 青の総和の 最小値を求めよ.


n = |match| <= 50

match[i] <= 100万

red[i], blue[i] <= 10000

----------

SRM396 1000 に似た問題が出ていて,

それは,マッチの合計を最大化する問題だった.

どの部分集合もxorが0 にならない ⇔ GF(2) で線形独立

である. 線形独立な列ベクトルの集合の族 はマトロイドになる(ベクトルトロイド).

そうすると,コスト関数が線形ならば, 貪欲で解ける.

SRM396 1000はそれで終わり.


今回は,線形でないので, なんとかして線形にしてやりたい.

最適解での赤の総和をR, 青の総和をB とする.

R,B をしっていれば,

w[i] = R * blue[i] + B * red[i] と置く(重みをバランスする)ことで

w[i] の総和が最小 ⇒ 赤の和 と 青の和 の積が最小(RB). となってくれる.

実際,ある解での赤の総和をr,青の総和をb とすると, (Rb + Br) = 2RB( (b/B + r/R)/2 ) >= 2RB( sqrt(br/BR) ) (相加相乗平均)

となり,br/BR >= 1 なので,右辺は 2RB 以上となり, (Rb + Br) >= RB + BR がいえた.


よって,R,B がわかると,w[i]の小さい順に貪欲に取っていけばよい.

今我々はR,B を知らないが, 考えてみると, R,B を使う理由は, 封筒をとっていく順番を決めるために過ぎない. つまり,R/Bのみが重要である.

R/B を0から無限大まで増やしていくことを考える.

ある2つの封筒の順序が入れ替わる境界値を t とし,それに 0, ∞ を加えたものを ボーダーと呼ぶことにし,

ボーダーを ソートして並べた列を考えると, 封筒の順序は,明らかに ボーダーボーダーの間の区間 では変化しない.

よって,例えば,隣り合うボーダーの中点をサンプリングしてやれば良い.


線形独立性のテストは,ビット演算を使うことにすれば n*20 くらいでできて, n^3 * 20 くらいの時間で解ける.

 |