ARC 201-300/ARC201F - CatCoder Triple Contest - 競技プログラミング用 知識集積所【6/24更新】

---

問題

ARC201F

必要知識

簡単な内容は省略

• 特になし

考え方

A問題の別解の方法が、この問題でも使える。

つまり、最終的に

• Div.1に優先的に問題を回したが、Div.1で出せるものがなくなった
• Div.2に優先的に問題を回したが、Div.2で出せるものがなくなった
• Div.3に優先的に問題を回したが、Div.3で出せるものがなくなった
• Div.1とDiv.2に優先的に問題を回したが、Div.1やDiv.2で出せるものがなくなった
• Div.2とDiv.3に優先的に問題を回したが、Div.2やDiv.3で出せるものがなくなった
• Div.1とDiv.3に優先的に問題を回したが、Div.1やDiv.3で出せるものがなくなった
• 問題が残り2セット以下になったために出せるものがなくなった

のいずれかが発生したら終了となるから

• Div.1に優先的に問題を回したら、Div.1でいくつ出せるのか
• Div.2に優先的に問題を回したら、Div.2でいくつ出せるのか
• Div.3に優先的に問題を回したら、Div.3でいくつ出せるのか
• Div.1とDiv.2に優先的に問題を回したら、最大何ペア出せるのか（Div.1かDiv.2かは無視して数える）
• Div.2とDiv.3に優先的に問題を回したが、最大何ペア出せるのか（Div.2かDiv.3かは無視して数える）
• Div.1とDiv.3に優先的に問題を回したが、最大何ペア出せるのか（Div.1かDiv.3かは無視して数える）
• 問題が残り2セット以下になるまでに、最大何トリオ出せるのか（Div.1かDiv.2かDiv.3かは無視して数える）

の最小値を答えるだけでいける。

あとは、これを各人ごとのループと問題ごとのループの二重ループの中に入れてやればよい。

解答例

解答例

注意点

Div.1とDiv.3に優先的に問題を回すパターンの必要性

Div.1かDiv.3につかえるというのは、Div.2にもつかえるわけで、一見必要性がよくわからない。
しかし、この条件を抜くと、次のようなケースでWAする。

1 2
0 2 2 2 0
1 1 1 1 1

別解