はじめに
最近競技プログラミングを始めたクソザコナメクジです。
よろしくお願いします。
先日のAtCoder Beginner Contest(通称ABC) 147回のC問題が個人的に難しかったので、勉強がてら説明を書いてみました。
合ってるかな？とか伝わるかしら？とか色々不安はありますがとりあえず書いてみようと思います。
問題を説明してみた！ってエントリなので当然ですが答えが出てきます。
まだ解いてないよって人は読まないほうがいいと思います。
どんな問題なの？
問題はAtCoderのサイトで見れるのでそちらを見てください。
https://atcoder.jp/contests/abc147/tasks/abc147_c
解いているときに躓いた点
$N$人の証言にムジュンがあるかどうか、数学的に色々ゴニョゴニョしないとわからないんじゃないかと思ってロジックを考え出して結局わかりませんでした！
あとは、不親切な人を嘘つき（必ず虚偽を言う人）だと勘違いしてたのがだめでした。問題文はちゃんと読もう。
解き方
AtCoderに掲載されている解説をベースに、解き方を自分なりに説明してみます。
ムジュンを調べてみよう
まずは、証言がどういう場合にムジュンしてしまうのか考えてみます。
3人の人が、以下のような証言をしている場合を考えてみましょう。（問題の入力例1と同じ状況です）
1さんは、2さんのことを正直者だと言っています。
2さんは、1さんのことを正直者だと言っています。
3さんは、2さんのことを不親切だと言っています。
この状況で全員が正直者だと仮定すると、証言と仮定の間にムジュンが生じてしまいます。
なぜなら、3さんが正直者だとすると、2さんは不親切な人です。
ですが、全員が正直者だと仮定していますから、2さんは正直者のはずです。
つまり、ある人$i$さんの状態（正直か不親切か）を仮定したときに、他の人の$i$さんに関する証言と齟齬が発生すればムジュンしてしまうと考えることができます。
ちなみに、重要なファクターなんですけど、不親切だと仮定した人の証言は無視してよいです。（不親切な人の証言は合っていても間違っていても関係ないのです）
ここまでの実装
なんとなくコードにしてみると、以下のような実装で調べられそうです。
変数は問題文と同じ文字ですが、
- $A_i$は$i$さんが証言した数
- $x_{ij}$は$i$さんの証言が誰についてのものか
- $y_{ij}$は$x_{ij}$さんが正直者かどうか
を示す変数です。
あと、getState(x[i][j])はx[i][j]さんの状態を取得する関数ですが、説明を簡略化するために登場させただけです。（本物の解説には出てきません）
/* N人についてのループ */
for(int i = 1; i <= N; ++i){
/* iさんの証言について調べるループ */
for(int j = 1; j <= A[i]; ++j){
if(getState(x[i][j]) == y[i][j]){
// ムジュンしない
}else{
// ムジュンする
}
}
}
最大値の調べ方
$N$人の状態がわかっていれば、証言とムジュンするかどうかは調べることができました。では、次にそれをすべての場合で調べるにはどうすればいいか考えてみます。
先程も書いたとおり、$N$人の人それぞれについて、正直者であるか不親切な人であるかを仮定すれば、その状態が証言と矛盾しないかは調べることができますね。
これをすべての場合について考えれば、正直者が一番多いパターンがわかるわけですが、$N$人が正直者か不親切な人であるかは、高々$2^N$通りしかありません。
これをどう実装していくか考えていきましょう。
ここまでの実装
まず、問題では$x_{ij}$さんの状態を$y_{ij}$が0か1かで表現していました。
これをそのまま利用することができそうです。
先程と同じく、入力例1の場合を考えてみます。
正直者が最大のとき、1さん、2さんは正直者、3さんだけが不親切でした。
これを数字で表現すると、011のように表現できそうです。（右から数えるのがポイントです）
各桁は0か1しか取りませんから、この数字の列を2進数として捉えることもできます。
そうすると、$N$人の取りうるすべての場合について調べることは、000から111までのすべての数について（証言とのムジュンがないか）調べることと同じことになります。
以下の実装では、変数bitsが、$N$人それぞれの状態（親切かどうか）を表現しています。
// すべての場合についてのループ
for(int bits = 0; bits < (1 << N); bits++) {
// ここでムジュンを調べる
}
解説ではbit全探索という言葉が出てきますが、このようにbitを使って部分集合のすべてを調べ上げる手法のことみたいです。
ビット演算 (bit 演算) の使い方を総特集！ 〜 マスクビットから bit DP まで 〜
ちなみに、bit全探索だと$N$が増加すると指数関数的に計算量が増大してしまうのですが、今回の問題では$N\leq15$という制限があるので、心配なさそうです。
まとめると
これまでの実装を組み合わせれば問題が解けそうです。
というか、実は今までの説明はkyort0n様の以下の実装を分解して考えたものになります。
https://atcoder.jp/contests/abc147/submissions/8830089
bit演算に馴染みがないと読むのに苦労するかもしれませんが、一行一行コメントをつけながら読んでいけばなんとかなりました！
やる気があれば、また今度自分で実装してここに載せようと思います。
おわりに
今回のC問題は一見とても難しそうだったのですが、解説を読んで分解してみると「なるほどなー！」って感じでした。実装例も最初はわからんちんでしたが、調べながら読み進めるとおもしろかったです。