キーエンスプログラミングコンテスト2022(AtCoder Beginner Contest 274) F - Fishing (500)
最初の考察
最大値が変わる場合があるのは二匹の魚が入れ替わるタイミングだろう
入れ替わる回数は$ \mathcal{O}(N^2)でそのときの最大値を求めるのは$ \mathcal{O}(N)とすると全体で$ \mathcal{O}(N^3)で間に合わない
最終的な考察
範囲の上限を全ての時間においてある魚の位置とする
それ以外の場所を端にするのは区間が無駄になる
これをそれぞれの魚$ iを基準として考える
他の全ての魚$ jについて範囲内に入って出るタイミングを求めてimos法で最大値を求める
入ってくるタイミングで$ +1、出るタイミングで$ -1する
出るタイミングは入ってくるタイミングで最大値を更新した後になるので極小値を足したり分けて値を持ったりする
$ dx = |x_i - x_j|, dy = |y_i - y_j| としておく
$ x_i \lt x_jの場合
$ y_i \le y_jなら範囲外に入ってくることは無い
そうでないなら$ \frac{dx}{dy}後に範囲内に入り、その$ \frac{A}{dy}後に範囲外に出る
$ dx \le Aの場合
時刻0で既に範囲内にいる
$ dy = 0なら最後まで範囲内にいる
$ y_i \gt y_jなら段々遠ざかるので$ \frac{A-dx}{dy}後に範囲外に出る
$ y_i \lt y_jなら段々近づくので$ \frac{A}{dy}後に範囲外に出る
それ以外の場合
$ y_i \ge y_jなら遠ざかるだけで範囲外に入ってくることは無い
そうでないなら$ \frac{dx-A}{dy}後に範囲内に入り、その$ \frac{A}{dy}後に範囲外に出る
個々の最大値が$ \mathcal{O}(N \log N)で求まるので全体で$ \mathcal{O}(N^2 \log N)