ABC 401-500/ABC418C - Flush - 競技プログラミング用 知識集積所【8/10更新】

---

問題

ABC418C

必要知識

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

• メモ化※

考え方

まず、愚直にやるのもそこそこ難しいので、実行時間制限がなかった場合を考える。

入力例の3番目のクエリを見てみる。
14個が最小値ということは、13個ならディーラーが勝てるということである。
これは、{4,1,4,4}個渡せばいい。

入力例の4番目のクエリを見てみる。
5個が最小値ということは、4個ならディーラーが勝てるということである。
これは、{1,1,1,1}個渡せばいい。

つまり、難易度bの場合、

• そもそもb個以上あるティーバッグがなければどうやっても負け
• それ以外の場合、それぞれb-1個（足りない場合はあるだけ全部）渡すのがディーラーが勝てる限界で、それより1大きければ自分の勝ちである。

ということで、各クエリごとに、「aの各要素とb-1の小さい方を全部合計」に+1すれば、愚直解である。

しかし、これでは毎回N回の計算が必要になり、それをQ回やるので最悪10^10回の計算が必要。
よって高速化を考える必要がある。

再び入力例1を見る。
仮にクエリとして3が与えられた場合、ディーラーが勝てる最大値は{2,1,2,2}の7個である。
これは、もちろん「aの各要素とb-1の小さい方を全部合計」したとも考えられるが、別の見方もできる。
それは、クエリで2が来た場合の{1,1,1,1}と比べて、2個以上あるティーバッグ全種1つずつ追加したという見方。
これを考えると、「クエリで2が来た時の答えが4+1」「2個以上あるティーバッグは3種類」という情報があれば、「クエリで3が来た時の答えが(4+3)+1=8」と簡単に求められる。

つまり、「Aの中にi以上の値は何個あるか？」に高速に答えることが高速化の鍵。
これは、Aをソートしてしまえば、二分探索※なり併走型の線形探索※なりで簡単。

以上の考えで、前から順に「クエリで1が来た時の答え」「クエリで2が来た時の答え」「クエリで3が来た時の答え」……「クエリで100000が来た時の答え」を用意することができる。
それを事前に済ませてメモ化※しておけば、クエリが来るたびに答えをメモから探して答えるだけである。
（aの最大値より大きい場合は-1であることをここまでちゃんと覚えている必要はあるが……）

解答例

解答例

注意点

答えがint型に入らない場合がある

全ティーバッグが大量に用意されているとすると、答えは3*10^11くらいまでありうる。
long long型を用意しておくこと。

別解