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"

先頭からの試合数を $x$ 座標、勝利数を $y$ 座標とする。
各時点の座標を、累積点 tmp として記録する。

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

result を $0$ で初期化する。
l1=0, l2=0 とし、下側凸包 d は空の状態から始める。

result: 0
d: {}

r=0 から r=5 までは、tmp[r] の $y$ 座標が $4$ 未満である。
したがって、$y$ 座標の差が $k=4$ 以上になる左端候補は存在しない。
d は空のままである。

r=6 では、tmp[6]=(6,4) となる。
tmp[0]=(0,0) との $y$ 座標の差が $4$ なので、tmp[0] を d に追加する。
l1 は $1$ まで進む。

d: {(0, 0)}
l1: 1

d の点は $1$ 個だけなので、l2=0 のままである。
tmp[6] と d[0] を結ぶ直線の傾きは、次のようになる。

$$
\frac{4-0}{6-0}=\frac{2}{3}
$$

これは、第 $1$ 試合から第 $6$ 試合までを選んだときの勝率に対応する。
この値で result を更新する。

result: 2/3

r=7 では、tmp[7]=(7,4) となる。
tmp[1]=(1,1) との $y$ 座標の差は $3$ である。
新しい左端候補は追加されない。
tmp[7] と d[0] を結ぶ直線の傾きは、次のようになる。

$$
\frac{4-0}{7-0}=\frac{4}{7}
$$

この値は $2/3$ より小さいので、result は更新しない。

r=8 でも、新しい左端候補は追加されない。
tmp[8]=(8,4) と d[0] を結ぶ直線の傾きは、次のようになる。

$$
\frac{4-0}{8-0}=\frac{1}{2}
$$

この値も $2/3$ より小さいので、result は更新しない。

r=9 では、tmp[9]=(9,5) となる。
tmp[1]=(1,1) との $y$ 座標の差が $4$ なので、tmp[1] を d に追加する。

d: {(0, 0), (1, 1)}

続いて、tmp[2]=(2,1) との $y$ 座標の差も $4$ なので、tmp[2] を追加する。
このとき、tmp[1] は下側凸包上に残らないので、d から削除する。

d: {(0, 0), (2, 1)}
l1: 3

次に、l2 が示す点を調べる。
tmp[9] と d[0]=(0,0) を結ぶ直線の傾きは、次のようになる。

$$
\frac{5-0}{9-0}=\frac{5}{9}
$$

tmp[9] と d[1]=(2,1) を結ぶ直線の傾きは、次のようになる。

$$
\frac{5-1}{9-2}=\frac{4}{7}
$$

$5/9<4/7$ なので、l2 を $0$ から $1$ へ進める。

l2: 1

このときの傾き $4/7$ は、現在の result である $2/3$ より小さい。
そのため、result は更新しない。

r=10 では、tmp[10]=(10,5) となる。
新しい左端候補は追加されず、d と l2 は変わらない。
tmp[10] と d[1]=(2,1) を結ぶ直線の傾きは、次のようになる。

$$
\frac{5-1}{10-2}=\frac{1}{2}
$$

この値も $2/3$ より小さいので、result は更新しない。
すべての r を調べ終えたとき、最大の傾きは $2/3$ である。

コードでは小数点以下 $10$ 桁で出力する。
最終的な出力は次のようになる。

0.6666666667

注意点

外積や傾きの比較に用いる積は、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)$ となる。