0.はじめに

今回も、プログラミング言語はC#を使用しています。

1.問題文

1 から N までの番号がついた N 人の人がいます。彼らはみな、必ず正しい証言を行う「正直者」か、真偽不明の証言を行う「不親切な人」のいずれかです。

人 i は A(i) 個の証言を行っています。人 i の j 個目の証言は 2 つの整数 x (i, j) , y (i, j) で表され、 y (i, j)=1 のときは「人 x (i, j) は正直者である」という証言であり、 y (i ,j)= 0 のときは「人 x (i , j) は不親切な人である」という証言です。

この N 人の中には最大で何人の正直者が存在し得るでしょうか？

2.制約

入力は全て整数
1 ≤ N ≤ 15
0 ≤ A(i) ≤ N − 1
1 ≤ x(i, j) ≤ N
x (i ,j) ≠ i
x (i , j_1) ≠ x (i , j_2) ( j_1 ≠ j _2 )
y (i, j)= 0 , 1

3.入力例

入力

出力

人 1 と人 2 が正直者であり、人 3 が不親切な人であると仮定すると、正直者は 2 人であり、矛盾が生じません。これが存在し得る正直者の最大人数です。

4.初見の感想

どういう風に正直者を割り当てるべきか見当がつかない
正直者か不親切かの２択しかない（選択肢が少ない）
制約のNが15以下から、N人それぞれが正直者か不親切かの全パターンを考える全探索を決行

5.学びポイント

対応関係が必要なので二次元配列で実装しました
全探索はN人分の配列tempに0か1かを入れておき、証言と合ってるかどうかをチェックします
無い配列を参照しないように細かい条件文を使っています

6.コードと簡単な解説

using System;
using System.Linq;
using System.Collections.Generic;
class Program
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());
        int[,] x = new int[N, N];
        int[,] y = new int[N, N];
        //入力をxとyの配列に入れる
        for (int i = 0; i < N; i++)
        {
            int num = int.Parse(Console.ReadLine());
            for(int j = 0; j < num; j++)
            {
                string[] input = Console.ReadLine().Split();
                x[i,j] = int.Parse(input[0]);
                y[i, j] = int.Parse(input[1]);
            }
        }
        int[] temp = new int[N];
        //全探索用の配列の初期化
        for (int i = 0; i < N; i++)
        {
            temp[i] = 0;
        }
        //2^N回の全探索
        int ans = 0;
        for (int loop = 0; loop < Math.Pow(2, N); loop++)
        {
            bool flag = true;
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < N; j++)
                {
                    //正直者の証言が間違っていないか判定
                    if (temp[i] == 1)
                    {
                        //値が0となっている配列はスキップ
                        if (x[i,j]!=0&&temp[x[i, j] - 1] != y[i, j]) { flag = false; }
                    }
                }
            }
            if (flag == true) { ans = Math.Max(ans,temp.Sum() ); }
            //全探索の更新処理
            temp[0] += 1;
            for (int i = 0; i < N; i++)
            {
                //temp[N]を触らないよう気をつける
                if (i != N - 1 && temp[i] == 2) { temp[i + 1] += 1; temp[i] = 0; }
            }
        }
        Console.WriteLine(ans);
    }
}

7.最後に

解いた瞬間では水パフォだったので驚きでした…(その後緑に落ちていきましたが)

ねむーの日記~AtCoderな日々~

福岡に住むプログラミング好きのブログです！

AtCoder Beginner Contest 147 C - HonestOrUnkind2