ABC 401-500/ABC445D - Reconstruct Chocolate - 競技プログラミング用 知識集積所

---

問題

ABC445D

必要知識

B以下レベルの内容は省略

• 考察問題

考え方

考察問題。

以下の方法で、ピース生成を再現することができる。
まず、残っているピースのうち、「最も縦幅が長いもの」「最も横幅が長いもの」をすぐに取り出せるようにしておく。
元々のサイズのチョコレートを用意し、以下を繰り返す。

• 「最も縦幅が長いもの」の縦幅が残っているチョコレートの縦幅と同じなら、チョコレートの右端部分を使ってそのピースを作る。
• 「最も横幅が長いもの」の横幅が残っているチョコレートの横幅と同じなら、チョコレートの下端部分を使ってそのピースを作る。

ピースの作り方の制約上、どちらかに該当するピースは必ず存在するため、最後の1ピースまで、作成を再現できる。

問題は、残っているピースのうち、「最も縦幅が長いもの」「最も横幅が長いもの」をすぐに取り出せるようにしておく方法。
2つのpriority_queue※を使う方法では、「最も縦幅が長いもの」を作った時に横幅側から削除するのが大変。
set※を2つ用意し、データの入れ方（ソート順と重複対応）を工夫するのが最も楽だと思われる。

解答例

解答例

注意点

別解