問題
考察
条件を満たし、かつ価値の和が最大となる贈り物の組み合わせを求めるという問題です。$N,M≦10^5$であることから、すべてのパターンを調べようとしても間に合わないことが予想されます。そこで計算量を落とすことができないか考えていきます。
もし、青木君への贈り物を1つ固定したとき、小さい計算量ですぬけ君への贈り物を決めることができるかを考えてみることにします。固定した青木君の贈り物の価値が$a$だとすると、すぬけ君への贈り物の価値は、$$a-D≦(すぬけ君への贈り物)≦a+D$$を満たす必要があります。
さらに考察を進めやすくするため$$(すぬけ君への贈り物)≦a+D \cdots (*)$$と条件を緩くした式で考えていきます。なくした不等号については後でつじつまを合わせればいいです。
ところで、すぬけ君への贈り物はできるだけ価値が大きいもののほうが良いはずです。なぜなら求めたいものは価値の和が最大のものであるためです。
ここまでの話から、すぬけ君への贈り物候補は$(*)$の条件式を満たし、その中で価値が最大のものとなります。これは二分探索を使えば$O(log M)$と小さい計算量で調べることができます。二分探索のアルゴリズムを実装してもよいですが、今回はC++の場合lower_boundやupper_boundという関数を使用する方法もあります。
二分探索を使ってすぬけ君への贈り物候補を調べました。この後は、緩くした条件のつじつまを合わせるために$$a-D≦(すぬけ君への贈り物)$$を満たしているかも調べましょう。もしすぬけ君への贈り物を調べている間に下記2点のいずれかに当てはまった場合、固定した青木君への贈り物についてはすぬけ君への贈り物として該当するものがないということになります。
- $(*)$を満たすものが1つもなかった。
- つじつま合わせの条件を満たさない。
これで青木君への贈り物を1つ固定したとき、小さい計算量ですぬけ君の贈り物を決めることができました。あとは青木君の贈り物全てですぬけ君への贈り物を調べてそれぞれの価値の和を比較していきます。そうすると計算量$O(NlogM)$で求めることができます。実行時間制限に十分間に合いそうです。
提出コード(コンテスト後)
ご不明点などがあれば教えていただけると幸いです。