A - Two Choices (ARC115)

問題リンク

感想

茶difだができなくてすごい落ち込んだ。そもそも問題文の意味理解にかなり苦戦した（１０分ぐらい...しかも結局誤読した）。
M=20と反射的にBIT演算でやろうとしたがうまくいかず。そこから思考停止に近い感じになってしまった。
この最初の方針で崩れた時に別の解放にスイッチができていないの致命的なので演習通して直していきたい。

自分の方針

まず、いつものforでbitの0,1で問題の正解を全列挙していく。その中で各N人の回答を比較して正解数をメモし、最後に全員の回答数が違うかどうかを判断する（listで各正解数を格納し、最後にset->len(list)みたいに）。
しかし、計算量がこの方針だとO(2^M * N)となり制限時間内に間に合わない。しかも、bit管理していると0000としたいところが0となってしまうなどのコレジャナイ感がすごいする。「何とかNを外して高速化できないかな？」みたいな錯誤してたら30分ぐらいたち、心が折れて解説ページに一目散。
ここで気づく、あくまで数え上げるのは組み合わせであったと。（「みんなの正解数がことなる正解セットを数えよ」という誤読をしていた。実際は「正解数を合わせることができない二組の個数を数えよ」であった。）

解法

シンプルに比べるとO(N*N)で到底間に合わないので工夫したいが、まず純粋に二組の正解数をどのように計測すればよいかを考える。まずは同じ回答をしている部分は取り除いても構わないので除外する（どうやっても二組の正解数の差には影響しないので）。
考えるべきは異なる回答をした部分についてだが、回答が異なるということは今回2値であることから必ずどちらかが正解するということはわかる。そこを考慮すると、どのような正解セットを用意しても、奇数個異なる回答をした場合は同じ正解数にはできないというところまではいける。まだこの時点で計算量は変わらずN**Nであるからもう少し考察を挟む。

ここで一歩引いて、「異なる部分が奇数個異なる」ということはどういうことか。二組をA,Bとする。

(1,0) OR (0,1)の部分が奇数個ある**(【AのI番目の回答、ＢのI番目の回答】)という表現
A,Bのすべての回答の１と０の偶奇が異なる

2については、上記の考察を踏まえていると自然に気づきそうではある。奇数個違う文字列に同じ組み合わせを付けたところで全体の偶奇が変わらないはず。
すると、「どんな回答が来ても正解数が同じものにならない二組」は1と0の偶奇が異なるものを選ぶ組み合わせの数を求めればよい。
なので、全体の1の回答数の偶奇を調べて、最後に（１が偶数個の人数）*（１が奇数個の人数）を出力すればACとなる。

まとめの感想

いや、むずくないか。これ本当に茶色diffなの...?今緑だがしっかりわからなかったし、解説聞いてもちゃんとコンテスト中に通せる自信がない。
あり本の典型だけでなく、このように自分で考察して解くみたいな問題ができないと水色には一生上がらなさそう。