AtCoder Beginner Contest 402 C - Dislike Foods

C - Dislike Foods

問題文は👆を確認してください

導入

atcoderで精進してますが、
どこかにアウトプットしたかったので、qiitaに書くことにしました。
ACしてから載せるようにしてますが、考え方が至っていない点があればご指摘頂けると幸いです。
また、誰かの参考になると嬉しいです。

使用しているアルゴリズム

貪欲法
(必要最小限の状態更新を貪欲にやる)

解法のポイント

この問題の肝は、毎日克服される食材が、どのメニューに影響するのかを効率よく調べることです。
NG実装のように毎日すべてのメニューを調べていると計算量が爆発してしまいます。

改善点は以下の通り：

• 食材→メニューのマッピングを defaultdict で保持（逆引き）
• 各メニューの「残り必要素材数」をカウント形式で保持し、0になったら達成済みとする
• これにより、毎日見るべきメニューを限定し、全探索を回避

---

NG実装例

N, M = map(int, input().split())

menus = []
for _ in range(M):
  menu = list(map(int, input().split()))
  menus.append((menu[0], set(menu[1:])))

menus.sort()
days = list(map(int, input().split()))
oks = set()
completes = [False] * M

for i in range(N):
  oks.add(days[i])
  for i, (k, menu) in enumerate(menus):
    if completes[i]:
      continue
    elif i + 1 < k:
      break
    if menu <= oks:
      completes[i] = True
  print(sum(completes))

❌ NG実装の問題点

• menus.sort() によるソートと break 判定の組み合わせが不自然かつ効果が薄い
• 毎日、すべてのメニューを1つずつ確認している（O(N×M×M)）ため、データ量が増えるとTLE必至
• 食材を克服したときに「関係あるメニューだけ更新する」構造になっていない

---

ACサンプル（改善後の実装）

from collections import defaultdict

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

menu_requirements = []  # 各メニューが必要とする素材数
ingredient_to_menus = defaultdict(list)  # 素材 → 使用しているメニューのインデックス

for menu_index in range(m):
    menu_info = list(map(int, input().split()))
    k = menu_info[0]
    menu_requirements.append(k)
    ingredients = menu_info[1:]

    for ingredient in ingredients:
        ingredient_to_menus[ingredient].append(menu_index)

days = list(map(int, input().split()))
completed_menus = 0

for ingredient in days:
    for menu_index in ingredient_to_menus[ingredient]:
        menu_requirements[menu_index] -= 1
        if menu_requirements[menu_index] == 0:
            completed_menus += 1
    print(completed_menus)

✅ 改善点まとめ

• 各素材に関係するメニューだけを更新
• menu_requirements を使って、素材を1つ克服するたびに O(I) だけの処理で済む
• 全体で O((N+M)×I) まで計算量を抑えられる

---

リンク

ACサンプル集(アルゴリズム逆引き)