ABC324の感想で述べたような解法(決して最小費用流とか)ではなく、平均を最大化する問題は二分探索で解けるというものだった。
あるパスの頂点を $p_1, ..., p_k$ とすると、今回の問題は、 $$ \frac{\sum_i^k b_{p_i}}{\sum_i^k c_{p_i}} $$ を最大化する問題になっている。
これをそのまま最大化しようとすると、パスを求めてからじゃないとコストがわからないような仕組みになっているので、 部分的な問題にできず、かなりよくない。部分的な問題にするにしてもコストを保存しないといけなくてとんでもない。
そこで、この問題をこの答えを $X$ 以上にできるかという判定問題にすると、 $$ \frac{\sum_i^k b_{p_i}}{\sum_i^k c_{p_i}} \geq X $$ となり式変形できる。 すると、 $$ \sum_i^k (b_{p_i} - X \times c_{p_i}) \geq 0 $$ という問題に変化する。 このようにすることで、このパスを求める際に部分問題が答えに使えるようになり、普通のdpで解けるようになるというものだ。
$X$ を t と命名したのは、特に意味はない。解いた時この変数名だっただけ。
少し解法らしいものを覗き見してしまった。それが判定問題について考えていたので、もしやと思ったら、解法が思い当たったので書いてみた。 そうしたらACした。うーん、蟻本にも乗ってるくらいの典型らしいけど、考えれば解ける問題だったなとも思う。 ちょっともったいないことしたかも・・・？
高橋くんとカード という問題でも、 計算量を減らすためにこういうテクニックが使われている(使わなくても解けるけど)。 平均を $A$ にしたいのであれば、 カードに対して最初から $A$ を引いてしまえば、個数によらず $0$ になるかどうかで判定できる という問題になっている。
二分探索の良いところは、問題が判定問題に落ちることによって、直接解を求める必要がなくなるというところだと思う。 実際に解になる値に対して、式変形が使えたり、決めうった $X$ を境界にしてデータが単純になったりする。 値の決め打ちは、式に介入できるということをしっかり覚えておこう。
最大化(最小化)するみたいな問題がでたときは、一回式を書いてみて、決めうったときに楽になるかを確かめるのが良いなと思った。 でも、本当に魔法みたいだ。具体的な値を出すだけで解け方が変わってくるのはかなり不思議な話だ。 Project Planning とかもかなりそうだけど。 まあこっちは判定問題の求め方がかなり特殊なタイプだけど。
ちなみに類題で 食塩水 という問題があるようだ。 これも同じように二分探索すると解くことができる。
(2023/10/19 00:27)