C - HonestOrUnkind2

[hxrxchang]

https://atcoder.jp/contests/abc147/tasks/abc147_c

問題概要

N人の人がいて、それぞれ"必ず正しい証言を行う正直者" か、"真偽不明な証言を言う不親切な人" のいずれかである。 各人が何人かの人に対して、その人が正直者か不親切な人かどちらかを証言する。 N人の中で最大何人正直者がいるか求めよ。

解き方

Nまでの人が正直者になるパターンをbit全探索で列挙する。 列挙したパターンごとに

• 正直者iが正直者だと証言した人がそのパターンに含まれていなければ矛盾
• 正直者iが不親切だと証言した人がそのパターンに含まれていれば矛盾

を検証していき、矛盾しなかったパターンの中で一番正直者の人数が多いものが答えになる。

func solve() {
    n := getInt()

    // graph[i]: 人iが正直者だと証言した人たち
    graph := make([][]int, n)

    // graph2[i]: 人iが不誠実だと証言した人たち
    graph2 := make([][]int, n)

    for i := 0; i < n; i++ {
        a := getInt()
        for j := 0; j < a; j++ {
            in := getInts()
            x, y := in[0]-1, in[1]
            if y == 1 {
                graph[i] = append(graph[i], x)
            } else {
                graph2[i] = append(graph2[i], x)
            }
        }
    }

    // 発言者を正直者とする組み合わせを列挙
    subsets := generateSubsets(rangeSlice(n))
    ans := 0

    for _, subset := range subsets {
        flag := true
        for _, v := range subset {
            // vを正直者だと仮定して、vが正直者だと言った人がsubsetに含まれていなければ矛盾
            for _, u := range graph[v] {
                if !sliceContains(subset, u) {
                    flag = false
                    break
                }
            }
            // vを正直者だと仮定して、vが不誠実だと言った人がsubsetに含まれていれば矛盾
            for _, u := range graph2[v] {
                if sliceContains(subset, u) {
                    flag = false
                    break
                }
            }
        }

        if flag {
            ans = max(ans, len(subset))
        }
    }

    fmt.Println(ans)
}

https://atcoder.jp/contests/abc147/submissions/55179522