buyoh.hateblo.jp

競プロ参加記録.開設したばかりなので暫くお待ちください.

yukicoder No.545 ママの大事な二人の子供

問題はこちら. - No.545 ママの大事な二人の子供 - yukicoder

コンテスト中に半分全列挙のアルゴリズムを調べ,書きなぐってAccept通したので,その考え方を書きます.

問題文

  • N 個のアイテムがある.
  • i 番目のアイテムをA君に渡すとA君はa_iポイント喜ぶ.
  • i 番目のアイテムをB君に渡すとB君はb_iポイント喜ぶ.
  • 適切に分配することで,2人の喜び度合いの合計の差をなるべく小さく抑えたい.

制約.

  • N は小さめだが,全探索は厳しい([tex:109]オーダー).
  • 喜怒哀楽が激しく,ポイントによる動的計画法が使えない.([tex:1010]オーダー)

半分全列挙

大まかな手法と流れと具体例

  • 次の入力を考える.
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と呼ぶことにする.
  • Sをsortする.
    • Sは(-11 -8 -6 -4 -3 -1 1 4)となる.
  • 集合Yの全てのパターンを試す.
    • 3つのアイテムを渡す組み合わせは,AAA,AAB,ABA,ABB,BAA,BAB,BBA,BBBの8通りが存在.
    • 例えば,BAAの組み合わせを試そうとする.
    • -8+7+9なので,8
    • Sの中からある要素eを取り出し,abs(8+e)が最小になるようなeを見つけたい.
      • Sはソート済みなので二部探索,三分探索が使える.

提出コード

#189130 No.545 ママの大事な二人の子供 - yukicoder