凸関数の最大値問題に帰着して三分探索（黄金分割探索）で計算します。

累積和を取ることで、点列の \(2\) 点を選ぶ問題に言い換える

文字列 \(S\) の文字 \(\mathtt{o}\) を \((1, 0)\)、\(\mathtt{x}\) を \((0, 1)\) と置き換え、さらに累積和をとることで点列 \(p_i = (x_i, y_i) \ (0 \le i \le N)\) が定義できます。

例

文字列 oxooxoxxox に対応する点列 $p$ は $$ (0, 0), (1, 0), (1, 1), (2, 1), (3, 1), (3, 2), (4, 2), \dots, (5, 5) $$ です。

このとき問題は次のように言い換えられます。

問題

高橋くんは以下の条件を満たすような $2$ 整数 $l, r$ を一つ選びます。

• $0 \le l < r \le N$
• $x_l + K \le x_r$

このとき、$f(l, r) = \displaystyle \frac {x_r - x_l}{(x_r - x_l) + (y_r - y_l)}$ としてあり得る値の最大値を求めてください。

言い換えた問題を解く

さて、この問題を \(r\) に関する全探索で解きましょう。\(r\) としては \(K \le x_r\) であるものだけを見ればよいですから、そうすることにしましょう。

さて、\(x_l \le x_r - K\) となる最大の \(l\) を \(l_{\mathrm{max}}\) と表すと、\(l\) の取りうる範囲は \([0, l_{\mathrm{max}}]\) であり、さらに \(l_{\mathrm{max}}\) は \(r\) に関して単調増加です。そこで、\(r\) を昇順に見ていき、尺取り法の要領で \(l_{\mathrm{max}}\) を管理しましょう。また点列 \(p_0, p_1, \dots, p_{l_{\mathrm{max}}}\) は、それらの点のうち、「最大を取りうる優秀なものだけ」を管理することを考えましょう。

そこで stack です。Stack を用いて点列 \(p\) の上凸包だけを管理することで、その上では \(f\) は上に凸な関数となります。あとは三分探索（黄金分割探索）をすればよいです。