AtCoder-ABC190 C - Bowls and Dishes【Python解答例】

AtCoder Beginner Contest190のC問題の解答例を記事にしていきます。
コンテストでも無事にACできた問題です。
AtCoder Beginner Contest 190 - AtCoder

AtCoder Beginner Contest190 C - Bowls and Dishes

C - Bowls and Dishes

問題文

1,2,…,N の番号がついた N 個の皿と、1,2,…,M の番号がついた M 個の条件があります。
条件 i は、皿 Ai と皿 Bi の両方にボールが (1 個以上) 置かれているとき満たされます。
1,2,…,K の番号がついた K 人の人がいて、人 i は皿 Ci か皿 Di のどちらか一方にボールを置きます。
満たされる条件の個数は最大でいくつでしょうか？

制約

・入力は全て整数
・2≤N≤100
・1≤M≤100
・1≤Ai

解答例

n, m = map(int,input().split())

A = []
B = []
for i in range(m):
    a, b = map(int,input().split())
    A.append(a)
    B.append(b)

k = int(input())

C = []
D = []
for i in range(k):
    c, d = map(int,input().split())
    C.append(c)
    D.append(d)

ans = 0
for i in range(2 ** k):
    dish = [0] * n
    for j in range(k):
        if (i >> j) & 1:
            dish[D[j]-1] += 1
        else:
            dish[C[j]-1] += 1
    sum_i = 0
    for l in range(m):
        if dish[A[l]-1] > 0 and dish[B[l]-1] > 0:
            sum_i += 1

    if ans < sum_i:
        ans = sum_i
else:
    print(ans)

解説

問題文を理解するのにけっこう時間がかかりました。

N枚の空の皿があってK人のひとがいます。
i番目のひとはCiかDiのどちらかの皿にボールを置けます。
みんながボールを置き終えた後で、AiとBiの両方の皿にボールが置いてあれば条件iが満たされたことになります。
条件が満たされた数を最大で何個にできるか解答する問題です。

K人のひとがボールを置く皿をbit全探索で決めて、満たされる条件の最大の個数を求めていきました。
コンテスト中に過去にbit全探索を練習した記事を参考にしました。
ebisuke33.hatenablog.com

dishリストはＮ枚の皿をあらわしていて初期条件ではボールがないのですべての要素は0にしました。
bitにあわせてCかＤの皿にボールが置かれたら、該当するdishリストの要素に1を足していきます。
これをK人全員に行って、ボールの配置を決めました。

ボールの配置が決まったあとは 条件を満たす数をかぞえるためsum_i変数を用意しました。
各条件に合致すればsum_i変数に1を足していきます。
最大のsum_iをans変数に格納することでACできました。

C問題ではbit全探索を使いましたが、過去に勉強したことが実際に使えてうれしかったです。
問題を理解してからbit全探索を思いつくまでの時間も短かったのですこしだけ身についてきたのかなって思いました。
初心者は成長を感じやすいところがいいですね！

ABC190の関連記事はこちら
ebisuke33.hatenablog.com
ebisuke33.hatenablog.com