ARC 201-300/ARC201A - CatCoder Double Contest - 競技プログラミング用 知識集積所

---

問題

ARC201A

必要知識

簡単な内容は省略

• 特になし

考え方

※別解の方がたぶんわかりやすい

各人の中で、各divにいくつ問題を出せるか考える。

各人の問題を横一列に並べる。
Div.1用にはHardもMediumも左から、Div.2にはMediumもEasyも右から使うことにする。
すると、Hard3問、Medium6問、Easy4問作った人は

Div.1用セット	セット1	セット2	セット3
Div.2用セット			セット4	セット3	セット2	セット1
Hard	問題1	問題2	問題3
Medium	問題1	問題2	問題3	問題4	問題5	問題6
Easy			問題4	問題3	問題2	問題1

というように、Div.1にだけ使えるセットが2つ、Civ.2にだけ使えるセットが3つ、どちらか不足している方に使えるセットが1つあるということになる。
それぞれのセット数は、大小関係に注意して場合分けなどをうまく使えば簡単に求められる。

各人に対してそれぞれを計算し、全員あわせて各セットがいくつできるかを数える。
コンテスト用のセットを作っていくと、最終的に

• どちらでも用を全部Div.1用に使ったが、Div.1で出せるものがなくなった
• どちらでも用を全部Div.2用に使ったが、Div.2で出せるものがなくなった
• 問題が残り1セット以下になったために出せるものがなくなった

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

解答例

解答例

注意点

別解

Div.1とDiv.2の個数に、どちらにも使えるやつを最初から足してしまう方がわかりやすい。
すなわち、最終的に

• どちらでも用を全部Div.1用に使ったが、Div.1で出せるものがなくなった
• どちらでも用を全部Div.2用に使ったが、Div.2で出せるものがなくなった
• 問題が残り1セット以下になったために出せるものがなくなった

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

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

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