yukicoder No.545 ママの大事な二人の子供
問題はこちら． - No.545 ママの大事な二人の子供 - yukicoder
コンテスト中に半分全列挙のアルゴリズムを調べ，書きなぐってAccept通したので，その考え方を書きます．
問題文
個のアイテムがある．
番目のアイテムをA君に渡すとA君は
ポイント喜ぶ．
ポイント喜ぶ．
- 適切に分配することで，2人の喜び度合いの合計の差をなるべく小さく抑えたい．
制約．
オーダー)．
- 喜怒哀楽が激しく，ポイントによる動的計画法が使えない．(
オーダー)
半分全列挙
- 計算量が
掛かる問題の一部は，
に抑えることが出来る
- ナップサック問題でも用いられることがある．
- ABC032-D解説に存在する．https://www.slideshare.net/chokudai/abc032
- 蟻本やスライドを軽く眺めるだけだけでは理解できず放置してたアルゴリズム．
大まかな手法と流れと具体例
- 次の入力を考える．
6 1 2 1 4 2 5 3 8 7 1 9 2
- 2つの集合に分割する．
{(1 2),(1 4),(2 5)}と{(3 8),(7 1),(9 2)}に分割できる．- 前者をX，後者をYと呼ぼう．集合Xの全てのパターンを試す．
- 集合Xの全てのパターンを試す．
- 3つのアイテムを渡す組み合わせは，
AAA,AAB,ABA,ABB,BAA,BAB,BBA,BBBの8通りが存在． - 試した結果の『2人の喜び度合いの合計の差』を求めvector等の可変長配列で記憶しておく．
- 『2人の喜び度合いの合計の差』は，
(1+1+2),(1+1-5),(1-4+2),(1-4-5),(-2+1+2),(-2+1-5),(-2-4+2),(-2-4-5)．これを可変長配列に保存する． - この結果を保持する配列をSと呼ぶことにする．
- 『2人の喜び度合いの合計の差』は，
- 3つのアイテムを渡す組み合わせは，
- Sをsortする．
- Sは
(-11 -8 -6 -4 -3 -1 1 4)となる．
- Sは
- 集合Yの全てのパターンを試す．
- 3つのアイテムを渡す組み合わせは，
AAA,AAB,ABA,ABB,BAA,BAB,BBA,BBBの8通りが存在． - 例えば，
BAAの組み合わせを試そうとする． -8+7+9なので，8- Sの中からある要素eを取り出し，abs(8+e)が最小になるようなeを見つけたい．
- Sはソート済みなので二部探索，三分探索が使える．
- 3つのアイテムを渡す組み合わせは，
