Matsushita's Blog

バレンタインデーの幸福度を最も高くするためにやるべき5つのステップ

問題

D: バレンタインデー - AtCoder Beginner Contest 018 | AtCoder

解法

グループにどの女子を含ませるか決まれば、どの男子を含めるべきかは貪欲に決定される。よって以下のステップで解くことができる。

  1. グループに含める女子を固定
  2. 幸福度が最も高くなるように、男子を決定
  3. 固定した女子の状態で最大の幸福度を算出
  4. どの女子をグループに含めるかを全てのパターンを列挙
  5. 最終的に幸福度が一番高いものを出力

bit操作によって女子のパターンを全列挙

グループにある女子を入れるか入れないか全てのパターンをbit操作を用いて全列挙を行う。2進数の桁数と女子の出席番号を一致せて考え、i桁目が1であれば出席番号iの女子がグループに含めるというように管理する。

また、今回はN人の女子の中からP人をグループに入れる。よって立っているフラグの数をカウントし、カウントがP以外はcontinueさせる。

女子を固定し、男子メンバーを考え幸福度を出す

ビット操作によって女子メンバーを固定した後は、男子メンバーを決定させる。以下のコードの配列scoressは、配列のインデックスと男子の出席番号を一致させて考え、出席番号iの男子を入れた場合の幸福度を格納していく。

ソースコード