ABC469 E - Pro Exam Eligibility

考え方

ある時点からある時点までの勝率の表現を言い換える。
$0$ 試合時点を含めた各タイミングでの（これまでの試合数、勝利数）を二次元プロットする。
$2$ 点を選んだ時に、それらから以下の情報が得られる。

• $x$ 座標の差が、その間の試合数
• $y$ 座標の差が、その間の勝利数
• その $2$ 点を通る直線の傾きが、勝率

ということで、プロットした点のうち、$y$ 座標の差が $k$ 以上あるなかでの傾き最大値を求めればよい。
単純に傾き最大なら凸包を作ればいいが、$y$ 座標の差が $k$ 以上という制限が普通にやると扱えない。

そこで、凸包（下側）を動的に作りながら調査をする。
以下の $3$ つのインデックスを持ちながら、尺取法とツーポインタ法を併走させる。

• r : 選ぶ $2$ 点の右側（ツーポインタ法用）、兼、「$y$ 座標の差が $k$ 以上」を調べる右側（尺取法用）
• l1 : 「$y$ 座標の差が $k$ 以上」を調べる左側（尺取法用）
• l2 : 選ぶ $2$ 点の左側（ツーポインタ法用）で、これだけ動的な凸包上を走る

$r$ を $1$ つ進めるごとに、以下を実行する。

• l1 を進めながら、r の示す点と「$y$ 座標の差が $k$ 以上」である点全ての凸包（下側）を作る。
• 点の追加によって凸包の点列が短くなって l2 がはみ出た場合、点列の最後に移動させる
• l2 を点列上で前に進めながら、r の示す点との傾きが最大になるところを探す
• r の示す点と l2 の示す点の傾きが最大記録だったら記録する

これで解ける。
実際には r の示す点と l2 の示す点の傾きが、その r についての最大値とは限らない。
しかし、その例外は、点列がまっすぐ $x$ 軸方向へ進んだ直後にしか発生しない。
よって、答えとなるべき最大値を見落とすことはない。

全ての点が定数回しか扱われないため、計算量は $O(N)$。

入力例1での動作

入力を受け取る。

n: 10
k: 4
s: "oxooxoxxox"

$0$ 試合時点も含めて、
各時点を（試合数、勝利数）の点で表すと次のようになる。

(0, 0)
(1, 1)
(2, 1)
(3, 2)
(4, 3)
(5, 3)
(6, 4)
(7, 4)
(8, 4)
(9, 5)
(10, 5)

右側の点を左から順に動かし、
勝利数の差が $4$ 以上になる点を左端候補へ追加していく。

右側が $(0,0)$ から $(5,3)$ までの間は、
勝利数の差が $4$ 以上になる左端候補は存在しない。

$(6,4)$ 以降の状態は次のようになる。

$(9,5)$ を見るときは、$(1,1)$ と $(2,1)$ が新しく左端候補になる。
$(1,1)$ を追加した後に $(2,1)$ を追加すると、
$(1,1)$ は下側凸包上に残らないため削除される。

また、$(9,5)$ から見た傾きは、
左端が $(0,0)$ なら $5/9$、$(2,1)$ なら $4/7$ である。
$5/9<4/7$ なので、$(2,1)$ の方を選ぶ。

各右端について得られる傾きの最大値を比べると、
全体で最大なのは $(0,0)$ と $(6,4)$ を選んだときの $2/3$ である。

したがって、答えは $2/3=0.666666\ldots$ となる。

注意点

外積や傾きの比較に用いる積は、int 型からはみ出る。
long long 型を用いること。

別解

勝率を固定したとき、その勝率以上を達成できる区間が存在するかは判定可能。
そして、その判定結果には単調性があるので、答えを二分探索できる。

$(試合数,勝利数-目標勝率\times 試合数)$ を二次元でプロットすることを考える。
どこかの $2$ 点を結んだ傾きが $0$ 以上になっていれば、その区間の勝率は目標勝率以上である。

ある大きな値 $G$ を設定し、一旦 $G\times$ 勝率の最大値を整数で求めることにする。
真の答えとの差は $1/G$ 未満なので、$G=10^7$ とすれば誤差は $10^{-7}$ 未満となる。
この場合、$(試合数,G\times 勝利数-(G\times 目標勝率)\times 試合数)$ をプロットすればよい。

勝利数は単調非減少なので、勝利数が $k$ 以上少ない範囲での最小値は尺取法で追加できる。
つまり、$G\times$ 勝率の候補 $1$ つの判定を $O(N)$ で行える。
二分探索分も考慮して、計算量は $O(N\log G)$ となる。