ABC147 C HonestOrUnkind2を解く

自分の考えを整理する目的で考察と実装をまとめていく。
実装は以下のAtCoder公式の解説を見た後、Python3にておこなった。

まずはじめに問題の考察をしていく。
問題は以下のリンク先で見ることができる。

C - HonestOrUnkind2

考察

求めるものは何か

N人のうち正直者であり得る最大人数

与えられているもの・条件は何か

正直者は本当のことを証言する。
不親切な人の証言は本当か嘘かは分からない。
人xは「人yは正直者ある」または「人yは不親切な人」という証言をする。（証言をしないこともある）

まず簡単な例で考える。
人1、人2、人3がそれぞれ次のように証言しているとする。

人1：人2は正直者である。人3は不親切な人である。
人2：人3は正直者である。
人3：証言なし。

3人全員が正直者であると仮定する。
このとき、正直者であると仮定する3人の組みは以下の1通りである。

正直者であると仮定する3人の組
1：人1、人2、人3

仮定と証言に矛盾がなければ正直者は3人である。

まず仮定より人1は正直者である。
人1の証言より人2は正直者であり、人3は不親切な人である。

しかし「3人全員が正直者である」という仮定より、人3は正直者であるので、人1の証言「人3は不親切な人である」と矛盾する。

したがって3人全員が正直者であることはあり得ない。

次に3人のうち2人が正直者であると仮定する。
このとき、正直者であると仮定する2人の組みは以下の3通りである。

正直者であると仮定する2人の組
1：人1、人2
2：人1、人3
3：人2、人3

人1と人2が正直者であるとき。

人3は不親切な人である。
人2の証言「人3は正直者である」は仮定に矛盾する。
よって人1、人2が正直者の組はあり得ない。

次に人1と人3が正直者であるとき。

人2は不親切な人である。
人1の証言「人2は正直者である」は仮定に矛盾する。
よって人1、人3が正直者である組はあり得ない。

最後に人2と人3が正直者であるとき。
人2の証言より人3は正直者である。
よって、仮定と正直者の証言に矛盾はなく人2、人3が正直者である組はあり得る。

ここまでで問題を理解できたと考えられるので具体例での考察を終える。

以上の考察から本問題を解く際のポイントは以下のようであると考えられる。

・正直者の人の組を全ての組合せで仮定する。
・正直者と仮定した人の証言が仮定に矛盾するとき、その正直者の選び方の組はあり得ない。
・正直者と仮定した人の証言同士の矛盾は調べる必要はない。ある人に対して矛盾する二つの証言があるとき、どちらか一方の証言は必ず仮定に矛盾する。したがって、この仮定があり得ないことを調べるには仮定と証言の矛盾を調べるだけでよい。
・全ての証言が矛盾しない正直者の選び方の組のうち、正直者が最も多い組の正直者の人数を求めれば良い。

実装する

以上の考察を元に実装していく。

人xの人yに対する証言のデータを二次元配列gへ次のような対応関係で格納しておく。なお、ここでは人の番号は配列のオフセットに合わせるため0から始めるものとする。

・人xが人yに対して正直者であると証言するとき、二次元配列g[x][y]を1にする。
・人xが人yに対して不親切な人であると証言するとき二次元配列g[x][y]を0とする。
・人xが人yに対して言及していないとき、二次元配列g[x][y]を-1にする。

詳細化しコードにしていく。

・入力よりNの最大が15なので、15行15列の二次元配列gをデフォルト値-1用意しておく
・全員の人数を表す値を受け取る。
・用意した配列に人iが人jに対して述べる証言のデータを格納していく。
・人iの証言の数mを受け取る。
・人iの証言を受け取るためm回次のループを回す。
・証言を表す二つの値を受け取り二次元配列gに格納する。人iが「人xはyである」と証言しているときg[i][x]=yである。（入力で受け取る「人の番号」は1から始まるため、コードでは受け取った値から1引いている。）

g = [[-1 for _ in range(15)] for _ in range(15)]
n = int(input())
for i in range(n):
 m = int(input())
 for j in range(m):
   x,y = map(int, input().split())
   g[i][x-1] = y

二次元配列gの作成と入力の受け取りは以上である。

次に問題を解く中心となるコードを実装していく。

まず、全ての正直者の組を表現するために二進数表記を用いることを考える。「人kが正直者であること」と二進数表記の対応関係を以下に示す。

二進数の右端の桁を0桁目とする。またkを0から14までの整数とする。
・「k桁目が1である」を「人kは正直者である」
・「k桁目が0である」を「人kは不親切な人である」
へとそれぞれ対応させる。

作り出した正直者の組それぞれに対して何らかの処理を行うため、これは全bit探索である。与えられる人数の最大値が15であるから、全bit探索の部分だけを考えると計算量は高々2^15の定数倍である。（後に全bit探索の中で2重ループと1重ループを回すことになるが、それを考慮しても計算量は高々2^15×(15^2+15)の定数倍であり10^6オーダーである。この計算量ではTLEにはならないと考えられる。）

以上の「正直者の組を作りだす」部分のコードは次のように実装できる。

・カウンタ変数iを1から2^15まで変化させ、次の処理を繰り返す。
・正直者の番号を格納する要素数nの配列honestsをデフォルト値0で作る。
・iを二進数で表現したときj桁目が1であればhonests[j]に1を追加する。

for i in range(1<<n):
 honests = [0 for _ in range(n)]
 for j in range(n):
   if (i>>j) &1:
     honests[j] = 1 

「honests[j]が1であること」は「人jは正直者であると仮定すること」に対応する。

次はhonestsの仮定と証言gに矛盾がないか調べ、求める値「N人のうち正直者であり得る最大人数」を出力するまでの実装をおこなう。
仮定と証言に矛盾があればそのhonestsで表現された組はあり得ない。

・求める値「N人のうち正直者であり得る最大人数」を格納するための変数ansをデフォルト値0で用意しておく。求める値は0以上の値であり以下のループ処理によって、より大きな値で更新され得る。最終的に最大値が格納される。
・ある正直者の組に矛盾がなかったことを表す変数okをデフォルト値Trueで用意しておく
・外側のループで配列honestsを作る。作ったhonestsの要素を順に調べる。honests[j]が1ならば証言g[j]は正しいのでg [j]を以下のように調べる。
・g[j][k]が-1ならば何もしなくてよいので次の証言を調べるループへ移る。
・g[i][k]がhonests[k]の値と異なるならばこの正直者の組はあり得ないので変数okをFalseにする。
・okがTureのときhonestsの要素の値が1であるものの数（つまり正直者の数）を数えてansより大きいならばその値をansに代入する。
・最終的なansの値を出力する。

以上を実装していく。先のコードへ追加する形でコードを示す。

for i in range(1<<n):
 honests = [0 for _ in range(n)]
 for j in range(n):
   if (i>>j) &1:
     honests[j] = 1 
 ok = True
 for j in range(n):
   if honests[j]:
     for k in range(n):
       if g[j][k] == -1: continue
       if g[j][k] != honests[k]: ok = False
 if ok:
   ans = max(ans, honests.count(1))

print(ans)

以下のリンク先のコードは実際に提出したコードである。

Submission #9337541 - AtCoder Beginner Contest 147

まとめ・学んだこと

・二進数表記を元に配列の各要素を0か1にしていくことで全ての組合せを表現できる。全bit探索をおこなうときに利用する。
・二次元配列listを作りlist[x][y]の値を「xからyを見たときの関係を表す値」とすることで、xからyを見たときの関係を二次元配列で扱うことができる。（有向グラフ？）
・1<<nで2のn乗を表すことができる。二進数表記の桁をn桁左にずらす演算である。