ARC043 B 難易度
問題文の条件を数式を用いて言い換える. 数列$ Dをソートしておいても一般性を失わないのであらかじめ昇順ソートしておく. すると「$ 2D_x \leq D_y, 2D_y \leq D_z, 2D_z \leq D_w(1 \leq x < y < z < w \leq N)なる$ (x, y, z, w)の組の個数を求めよ」という問題に帰着することができる. 以後, この問題を考えていく.
そこで$ D_yを固定することを考える(これは3文字の場合真ん中を固定することから, 4文字も真ん中に近い方を固定した方が考えやすいからである). すると$ D_xの個数については$ D_x \leq \lfloor D_y / 2 \rfloorと変形して二分探索することにより求められる. よって$ (z, w)の個数を求め, $ D_xの個数とかけ合わせればよいこととなる. さて, $ (z, w)の個数を求める. まず$ D_zの個数だが, これについては$ 2D_y \leq D_zなる$ zを二分探索によってそのまま求めればよいことになる. ここで条件を満たす$ zは必ず区間の形で存在している. そこで$ 2D_i \leq D_jなる$ jの個数を各$ iについて前計算しておくと, その累積和を用いることで各$ zごとの$ wの個数の総和, すなわち$ (z, w)の個数を求めることができる. よってこの問題を$ O(N log N)で解くことができた.