Fisher

便宜上 $A_0=0, A_{N+1}=L$ とします。
魚の座標が $x$ であるときのコストを $f(x)$ とおくとコストの期待値は $\frac{1}{L}\int_0^Lf(x)dx$ なので、$I=\int_0^Lf(x)dx=\sum_{i=0}^N\int_{A_i}^{A_{i+1}}f(x)dx$ を最小化すればよいです。

まずは次の問題を考えます。

• 座標 $A_i$ と $A_{i+1}$ の間にマシンを $k$ 台追加で設置するとき $\int_{A_i}^{A_{i+1}}f(x)dx$ の最小値はいくらか。

魚の座標が $A_i \le x \le A_{i+1}$ であるとき最も近いマシンの座標は $A_i \le y \le A_{i+1}$ であるため、$\int_{A_i}^{A_{i+1}}f(x)dx$ は他に追加する $M-k$ 台のマシンの座標には依存しないことに注意します。

• $i=0$ のとき、座標 $\frac{2j-1}{2k+1}A_1\,(1 \le j \le k,j \in \mathbb{Z})$ にマシンを設置すると $\int_{A_i}^{A_{i+1}}f(x)dx=\frac{{A_1}^2}{2(2k+1)}$ となりこれが最小です。
• $1 \le i \le N-1$ のとき、座標 $A_i+\frac{j}{k+1}(A_{i+1}-A_i)\,(1 \le j \le k,j \in \mathbb{Z})$ にマシンを設置すると $\int_{A_i}^{A_{i+1}}f(x)dx=\frac{(A_{i+1}-A_i)^2}{4(k+1)}$ となりこれが最小です。
• $i=N$ のとき、座標 $A_N+\frac{2j}{2k+1}(L-A_N)\,(1 \le j \le k,j \in \mathbb{Z})$ にマシンを設置すると $\int_{A_i}^{A_{i+1}}f(x)dx=\frac{(L-A_N)^2}{2(2k+1)}$ となりこれが最小です。

（直観的な説明：正の実数 $d$ に対して $f(x)=d$ を満たす $x\,(A_i \le x \le A_{i+1})$ の個数を $c(d)$ とおくと $c(d)$ は広義単調減少であり、$d$ を $0$ に近い値から大きくしていったときになるべく $c(d)$ の値が小さくならないようにしたいです。例えば $i=0$ のときは上記のようにマシンを設置すると $0 < d < \frac{A_1}{2k+1}$ の範囲で $c(d)=2k+1$ となります。）
（お詫び：厳密な証明ができていません。もしも間違っていたらすみません。）

あとは各 $i$ について座標 $A_i$ と $A_{i+1}$ の間に何台マシンを設置すれば $I$ が最小になるかを求めればよいです。
先ほどの部分問題において設置するマシンの台数を $k$ から $k+1$ に増やすとき、$\int_{A_i}^{A_{i+1}}f(x)dx$ の減少量（$=I$ の減少量）は次のようになります。

• $i=0$ のとき $\frac{{A_1}^2}{2(2k+1)} - \frac{{A_1}^2}{2\{2(k+1)+1\}} = \frac{{A_1}^2}{(2k+1)(2k+3)}$
• $1 \le i \le N-1$ のとき $\frac{(A_{i+1}-A_i)^2}{4(k+1)} - \frac{(A_{i+1}-A_i)^2}{4\{(k+1)+1\}} = \frac{(A_{i+1}-A_i)^2}{4(k+1)(k+2)}$
• $i=N$ のとき $\frac{(L-A_N)^2}{2(2k+1)} - \frac{(L-A_N)^2}{2\{2(k+1)+1\}} = \frac{(L-A_N)^2}{(2k+1)(2k+3)}$

いずれの場合も $I$ の減少量は $k$ に対して単調減少します。したがって、マシンを追加していない状態からスタートし、最も $I$ が減少するような $i$ を選んでマシンを $1$ 台ずつ追加していく貪欲法によって答えを求めることができます。これは優先度付きキューを用いて時間計算量 $O(M \log N)$ で計算できますが、このままでは実行時間制限に間に合わないため高速化が必要です。

この貪欲法において最後にマシンを追加するときの $I$ の減少量を二分探索することを考えると、各 $i$ についてマシンを追加する回数をそれぞれ $O(\log M)$ で求めることができ、$O(N \log M)$ で二分探索の判定問題を解くことが可能です。判定問題は $O(\log LM)$ 回解けばよいので全体で $O(N \log M \log LM)$ となり十分高速です。
なお二分探索時にちょうど $M$ 回マシンを追加できる値が存在するとは限らないため、$M-N$ 回程度追加できたら残りの回数分は愚直に貪欲法で求めるようにするとよいです。

以上により元の問題を $O(N (\log M \log LM + \log N + \log \mathrm{MOD}))$ で解くことができました。

実装時の注意点として、本問の制約の下では $I$ の減少量を倍精度以上の浮動小数点数で表したとき二分探索が停止することが示せますが、その後の貪欲法を正しく実行するためには四倍精度等の十分高い精度の浮動小数点数を用いるか、分数を分母と分子に分けて整数の組として扱う必要があります。

実装例（C++）