CPSCO2019 Session1 F - Fruits in Season
お題箱より。
解法
最小値の最大化問題です。このタイプの問題はまず二分探索を考えてみる価値があります。
判定問題として、ある に対して「果物の美味しさの最小値を
以上にできるか？」という問題を考えます。最小値の最大化問題についてこのような二分探索を考えると、2つの嬉しいことがあります。
1. 単調性が自動的に確保される
二分探索を適用できる条件として必要なのが単調性です。
「最小値を 以上にできるか？」という判定問題は、
が大きいほど条件が厳しい問題になります。ある
について条件を満たせば、それより小さい（条件の甘い）
については必ず条件を満たすので、自動的に単調性が確保されます。
2. 「貪欲」や「ギリギリまで粘る」など最適戦略が定まりやすい
果物の美味しさの最小値を 以上にすることは、全ての果物の美味しさを
以上にすることと同じです。
食べる日が旬から離れるほど果物の美味しさは減っていき、全ての果物をピッタリ旬に食べられるとは限りません。目標値が決まっていない状態では、1日ごとに美味しさが変動する果物のうちどれを優先すれば最小値を大きくできるのか決めづらいです。一方「全部 以上にする」という目標が決まっていれば、
以上である間はいつ食べても同じなので、「食べていい期間」と「食べられない期間」に分けることができます。
このように目標値を決めることで、それを達成できる/できない条件が明確化されます。今回の問題のように「どれを優先するか」で悩むような問題や、限られたリソースを各要素に配分するような問題では、目標値を決めることで最適戦略が定まることが多いです。
この問題における最適戦略
今回の問題は果物 の「食べていい期間」が区間になるので、以下のような戦略で割り当てていくことができます。
「今見ている日付を食べていい区間に含む、未割り当ての果物」を集合として管理しておきます。日付を早いほうから1日ずつ見ていきながら、以下の処理をします。
- 今見ている日が区間の左端である果物、つまり新しく食べられるようになった果物を集合に入れる。
- 今見ている日に割り当てる果物を決める。このとき区間の右端が最も左側にある果物、つまり猶予が最も短いような果物を選ぶのが最適である。
これで最後まで割り当てができた場合は判定問題の結果はYes、途中で割り当てる果物がなくなってしまったらNoです。
2で最も右端が左側にある区間を選ぶ操作は、集合を優先度付きキューとして管理していれば実現できます。集合に入れた後は右端の値しか使わないので、右端の値を単に整数として優先度付きキューに入れていけば良いです。
これで二分探索をすれば、解くことができます。
ACコード
Submission #5251240 - CPSCO2019 Session1
この問題の解法説明は公式解説とほぼ同じです。公式解説が十分丁寧に書かれているので、「最小値の最大化問題は二分探索するとなぜ上手くいくことが多いのか」というところをメインで書いてみました。
