バレンタインデーの幸福度を最も高くするためにやるべき５つのステップ
問題
D: バレンタインデー - AtCoder Beginner Contest 018 | AtCoder
解法
グループにどの女子を含ませるか決まれば、どの男子を含めるべきかは貪欲に決定される。よって以下のステップで解くことができる。
- グループに含める女子を固定
- 幸福度が最も高くなるように、男子を決定
- 固定した女子の状態で最大の幸福度を算出
- どの女子をグループに含めるかを全てのパターンを列挙
- 最終的に幸福度が一番高いものを出力
bit操作によって女子のパターンを全列挙
グループにある女子を入れるか入れないか全てのパターンをbit操作を用いて全列挙を行う。２進数の桁数と女子の出席番号を一致せて考え、i桁目が1であれば出席番号iの女子がグループに含めるというように管理する。
また、今回はN人の女子の中からP人をグループに入れる。よって立っているフラグの数をカウントし、カウントがP以外はcontinueさせる。
女子を固定し、男子メンバーを考え幸福度を出す
ビット操作によって女子メンバーを固定した後は、男子メンバーを決定させる。以下のコードの配列scoressは、配列のインデックスと男子の出席番号を一致させて考え、出席番号iの男子を入れた場合の幸福度を格納していく。
