AtCoder Beginner Contest 147　C問題 - 書きたいことを書きたいだけ。

実装力が無い、かつアルゴリズムに対する知識が無いと思ったので競プロ界隈を覗いてみた。
若いのに、すごい人が一杯いる。
凄い人と自分の差がスコアではっきり分かってしまうのはある意味、競技プロのいいところかもしれない。

当分は過去問を解くぐらいだけど、ある程度実力ついたらコンテストとかにも出てみたい。
そんな訳でABC147のC問題がいい問題らしいので解いてみた。
色々とあってC#で書いています。
他の人の実行時間とかと比べるとめちゃ遅いです。

一回目は全くちんぷんかんぷんな解答をしてしまったので、解説を見てからの実装です。
サンプルは合ってたんだよ。（言い訳）

using System;
using System.Linq;
using System.Collections.Generic;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            //入力部分,最初のN（人数）を読み取る
            var N = int.Parse(Console.ReadLine());
            var input_data = new List<List<int[]>>();

            //人数分の証言を読み取る
            for(int i = 0; i < N; i++)
            {
                var num_evidence = int.Parse(Console.ReadLine());
                var tmp = new List<int[]>();
                //特定の人の証言の数だけ読み取る
                for(int j= 0; j < num_evidence; j++)
                {
                    var evidence = Console.ReadLine().Split().Select(int.Parse).ToArray();
                    tmp.Add(evidence);
                }
                input_data.Add(tmp);
            }

            var max = 0;//正直者の最大値
            
            //仮定のパターンだけ繰り返す、1をNビットシフトさせた数。つまり2のN乗
            for (int i = 0; i < 1<<N ; i++)
            {
                var flag = true;//今回の仮定はすべてあってるかどうかを確認する
                for (int j = 0; j < N; j++)
                {
                    //仮定のパターンに対して１ビットずつ確認していく
                    if ((i >> j & 1) == 0) { continue; }//不誠実な人のパターンは無視
                    else
                    {
                        for(int k = 0; k < input_data[j].Count(); k++)
                        {
                            var num = input_data[j][k][0]-1;
                            if (((i >> num) & 1) != input_data[j][k][1])//パターンが一致しなかった
                            {
                                flag = false;
                            }
                        }
                    }
                }
                if (flag)//今回の仮定が正しかったので正直者の数を数える
                {
                    var c=0;//立っているビットの数、つまり正直者の数
                    for(int n = 0; n < N; n++)
                    {
                        if(((i >> n) & 1) == 1) { c++; }//１つずつずらして「1」が立っているビットの数を調べる
                    }
                    max = max > c ? max : c;
                }               
            }
            Console.WriteLine(max);
        }
    }
}

長いですがソースコード丸々です。
高々2の15乗ほどしかパターンしか無いので全部試してみるってやつです。
全ビット探索と言われるものらしい。
ソースにコメントを大量につけたので、ちょっとは理解しやすいと思う。

当たり前ですが、ソースは読み込み部と判定部に分かれていて、
標準入力から読み込んだデータは

var input_data = new List<List<int[]>>();

に放り込んで、例えばinput_data[0]で1人目の証言が取得できます。
1人が何個証言するかは入力によって違うけど、証言の数に応じて取得できます。
(例えば1人目が3個証言すると、input_data[0][0]、input_data[0][1]、input_data[0][2]が1人目の3つの証言）更に、input_data[0][0][0]だと１人目が誰に対しての証言、input_data[0][0][1]でその時の正直or不誠実のデータが取得できるっていう実装にしました。

判定部は、

for (int i = 0; i < 1<<N ; i++)

の部分から始まり、2のN乗のパターンだけ試行します。
つまり正直か不誠実な人の2択なので、2のN乗のパターンがあるのでそれらをすべて調べ上げる。
このfor文の中の1回の試行で、例えばN=3・i=3の時、i=3の3をビットにすると「011」になります。
この「011」を１人目から３人目まで「不誠実、正直、正直」パターンと置き換えて考えます。

最初のfor文の中で

for (int j = 0; j < N; j++)

ともう一度for文を回すことで、この例えば「不誠実、正直、正直」のパターンを１人目が不誠実な時、２人目が正直な時、と判定します。

if ((i >> j & 1) == 0)

この部分は不誠実だった場合は、そもそも意見がどっちか分からないので考えようがないし、答えは正直な数の人を求めるのでスルーしますって事です。
つまり、「不誠実、正直、正直」パターンを調べるときに１人目は不誠実なので特に判定せず、次の２人目の正直の判定に移ります。
２人目が正直パターンの場合、証言と一致するか確認します。
input_dataからinput_data[1]で２人目の証言データを取り出して判定します。
２人目の人が、「３人目の人は正直で、１人目の人は不誠実である」と証言した場合を考えてみましょう。
今、調べているパターンは「不誠実、正直、正直」でなおかつ２人目は正直であると仮定しています。
つまり「３人目の人は正直で、１人目の人は不誠実である」は絶対正しいわけです。
今、「不誠実、正直、正直」パターンを調べていて、「３人目の人は正直で、１人目の人は不誠実である」という意見は正しいので次に進みます。
次は３人目の正直の判定です。
3人目が正直だと仮定して、実際の３人目の証言が「１人目は正直で、２人目は不誠実であった。」と証言すると今、調べている「不誠実、正直、正直」と合わないわけです。

つまり、「不誠実、正直、正直」は成り立たないというわけです。
このようにN=3とすると８通り出てきますが、すべてのパターンに対して成り立つか成り立たないかを調べていきます。
そして成り立った場合には、正直者の数を数えます。

正直者の数を数えるには、成り立ったパターンのビットにしたやつの「1」が立っている数を数えればいいわけです。

 if(((i >> n) & 1) == 1) { c++; }

この部分です。
forで回しながらビットを1つずつずらして、１が立っているかどうかをカウントしています。

後は、今までの最も多かった正直者の数と比較して、大きければ現在の最も多かった正直者の数を更新して出力します。