けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 147 C - HonestOrUnkind2 (緑色, 300 点)

とても教育的な問題でしたね!!!
ここにまとめました!

drken1215.hatenablog.com

以下のような問題です。bit 全探索とよばれているもので、 2^{N} 通りの選択肢をすべて調べ上げる手法を用います。

問題概要

 N 人がいて、それぞれ「正直者」であるか、「不親切な人」であるかのいずれかです。

  • 「正直者」は、必ず、正しいことを語る
  • 「不親切な人」は、真偽不明のことを語る (正しいかや誤りかはわからない)

今、 N 人がそれぞれ次のように語りました。

  •  i 人目は、 A_i 個の証言を語った
    •  i 人目による  j 個目の証言は以下のいずれかである
      •  x_{i, j} さんは「正直者」です ( y_{i, j} = 1)
      •  x_{i, j} さんは「不親切な人」です ( y_{i, j} = 0)

 N 人それぞれの「正直者」であるか「不親切な人」であるかのパターンのうち、以上の証言に矛盾しないものはいくつか考えられます (0 通りもありえます)。そのうち、正直者が最も多いパターンでは、正直者は何人でしょうか?

制約

  •  1 \le N \le 15