ABC 402のC問題 Dislike Foodsの感想戦

2025-04-20

ABC 402 の C 問題 Dislike Foods の感想戦。食べられるようになる順番を逆にたどり、食べられない料理の集合を作ることで解決。さらに料理に使われる食材を見て食べられるようになる日に変換することで、よりスマートに解決する方法があることを知った。

AtCoder 東京海上日動プログラミングコンテスト 2025（AtCoder Beginner Contest 402）のC 問題 Dislike Foodsの感想戦

問題

料理ごとに使われている食材が提示される。日毎に食べられる食材が増えるので、その日までに食べられる料理の数を回答する。

方法

毎日食べられるようになった食材のみを含む料理を数える方法はループ回数が多くて計算時間の制限に引っかかる(LTE)。

そこで問題を逆に考えて、最後に食べられるようになる食材を含む料理は最後の日まで食べられない料理とする。

この考えを表現するために料理と使われている食材の二次元 List を作成し、食べられるようになる食材の順番を優先順位としてソートした。そうすれば、食べられるようになる順番に料理を並べ替えられる。しかしこの方法は、ソートに時間がかかりすぎるようで LTE となった。

ここで、料理に注目するのではなく食材に注目し、食材が使われている料理の集合を考えた。そうすると、食べられる逆順に食材を見ると、どの料理を食べられないかが見えてくる。最終日に食べられるようになった食材を含む料理は、その前日まで食べられなかった＝その料理以外は食べられることになる。

これを最終日から初日に向かって繰り返すと、食べられない料理の集合が増えていく。

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

items = [set() for _ in range(n + 1)]
for i in range(1, m + 1):
    dish = list(map(int, input().split()))
    for item in dish[1:]:
        items[item].add(i)

eat = list(map(int, input().split()))

ng = [m] * n
ng_dishes = set()
for i in range(n - 1, 0, -1):
    item = eat[i]
    ng_dishes |= items[item]
    ng[i - 1] = m - len(ng_dishes)
print(" ".join(list(map(str, ng))))

よりスマートな方法

正解できたので満足していたら、よりスマートな解法をXで見つけました。この方法では、料理に使われている食材リストを見て、結局何日目に食べられるようになるかを計算してしまいます。この日付を集計すれば答えとなります。

もう少し説明すると

食べられるようになる日にちが得られたら、食材から克服する日の変換表を作る。1 日目 →0
変換表で料理の食材を食べられるようになる日に変換して、その最大値を料理を食べられるようになる日とする。
食べられるようになった日の料理数の表を更新する。
最終結果は、その日までに食べられるようになっている数をカウントする。

となります。

この方法は、集合の merge が必要ないためか、自分で考えた方法よりも約 1.7 倍速く問題を解決できました。自分で考えた方法は 500ms 位かかりましたが、この方法は 300ms 位でした。

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

# memo items for dishes
dishes = []
for _ in range(m):
    dish = list(map(int, input().split()))
    dishes.append(dish[1:])

eat = list(map(int, input().split()))

# make a table to convert items to edible day
edible = [0] * (n + 1)
for day in range(n):
    item = eat[day]
    # edible date start at 0
    edible[item] = day

# determine the day to eat
ok = [0] * n
for items in dishes:
    max_day = 0
    for item in items:
        edible_date = edible[item]
        if edible_date > max_day:
            max_day = edible_date
    ok[max_day] += 1

# sum edible dishes.
sum = 0
ok_num = []
for i in range(n):
    sum += ok[i]
    ok_num.append(sum)
print(" ".join(list(map(str, ok_num))))

参考サイト

六月 @june19312