ABC374 E - Sensor Optimization Dilemma 2
NWJ.icon
問題概要
ある製品の製造には工程$ 1, \cdots, Nを経なければならない。
各工程$ iごとに、処理する機械が二種類あり、それらを$ 0台以上導入できる。
$ S_i: $ A_i個/日の製品を処理できる（$ P_i円/台）
$ T_i: $ B_i個/日の製品を処理できる（$ Q_i円/台）
導入した結果工程$ iで$ W_i個/日の製品を作れるようになったとする。
今、予算が$ X円あったとする。
この工程のボトルネックとなる箇所の処理能力$ \min_{i} W_iをできるだけ大きくしたい。
$ \min_{i} W_iを最大化せよ。
コンテスト中
線形計画法なのかなって思ったけど、min_{i = 1}^{N}が厄介 どうすればよかったんだろう 主シンプレックス法だったのかな....。
解法
0. 「$ X円の予算のもとで処理能力を$ W以上にすることはできるか？」という問題を十分早く解くことさえできれば、あとは二分探索できる。 こうすることで、最小値の評価を考える必要はなくなり、代わりに全ての$ iに対して、$ W_iが$ W以上になるかを調べる問題に集中できる。
1. $ X円の予算のもとで、全ての$ W_iに関して$ W_iは$ W以上になるか？
しかし、何に対して走査する？探索空間をどう定めるかが問題。
$ s_i, t_iは機械$ S_i, T_iの購入個数として
$ W_i = s_i A_i + t_iB_i \geq W
$ \sum_{i}(s_i P_i + t_i Q_i) < X
なる$ s_i, t_iの候補を列挙できるだろうか？
まず、ありうる$ \{(s_i, t_i)\}_i \sub \N^2を全部列挙するのはしんどい
最悪$ O(((W/A_i)(W/B_i))^N)のループになる。
値段ベースで限らせても、問題は解決しない
各工程は独立に考えたいし、$ s_i, t_iの探索範囲を十分に限らせたい
2. もう一段階問題を言い換えて、各工程を独立にする。
工程$ iにおいて$ W_i \geq Wを達成する最小の予算は何か？
全ての工程に関してこれらを足し上げた予算が$ Xを越えない場合に限り、$ X円の予算のもとで全ての$ W_iを$ W以上にできる。
こうすることで、各工程を独立に考えられる。
じゃあ、$ (s_i, t_i) \in \N^2を全部列挙すればいい？
これもしんどい
$ O((W/A_i)(W/B_i))は時によっては莫大な数になる。
$ s_i, t_iに関して限定できないか
3. 最適解であることを用いて、$ s_i, t_iに制約をつける。
定理: 購入した$ S_i, T_iの一方において、$ A_iB_i個分以下の処理能力しか持たせないようにしても問題ない $ S_i, T_iがそれぞれ$ B_i + s_i, A_i + t_i台導入する戦略を考える。
この時、コストに関してより最適な戦略が存在する。
製造能力としては$ (A_iB_i + s_iA_i) + (A_iB_i + t_iB_i)台生産できて
コストとしては$ (A_iP_i + s_iP_i) + (B_iQ_i + t_iQ_i)円
$ A_iB_i台生産できる能力は、より安い方にとっかえた方が良い。
$ S_i, T_iがそれぞれ$ B_i台, $ A_i台ある時の生産能力は両者とも同じ
仮に$ A_iP_i < B_iQ_iだったときを考えよう
$ S_i, T_iをそれぞれ$ s_i, A_i + A_i + t_i台導入する戦略に変えると
生産台数は変わっていないのに、コストを安くすることができた。
従って両者$ S_i, T_i共に$ A_iB_i個分以上の処理能力を持っているような戦略は最適ではない。
待遇をとって
最適な戦略であれば、$ S_i, T_iのうち一方が$ A_iB_i個分以下の処理能力を持っている。
従って、
$ A_iP_i \leq B_iQ_iであれば、$ s_i \leq B_iのもとで最低限必要な$ T_iの台数$ t_iを求めて
$ A_iP_i > B_iQ_iであれば、$ t_i \leq A_iのもとで最低限必要な$ S_iの台数$ s_iを求めて
それぞれの$ s_i, t_iの組み合わせを探索して最低予算を求めれば良い。
計算量は$ O(\max\{A_i, B_i\}) 最後にその求めた最低予算を足し合わせれば良い！
$ O(N\max\{A_i, B_i\})
それを二分探索すれば良いから、$ \log(X(A_i + B_i))ステップ
$ X(A_i + B_i)は$ Wの上界
$ O(N\max\{A_i, B_i\}\log(X(A_i + B_i)))
実装
WJ.icon 実装