AtCoder Regular Contest 075 E - Meaningful Mean - アルゴリズマーの備忘録

ARCのEは解けるようにならないと不味い。

問題概要

N個数列のN*(N+1)/2個の空でない部分列のうち、算術平均がK以上のものはいくつあるか。

http://arc075.contest.atcoder.jp/tasks/arc075_c

解説

仮平均をすると楽なので、各a[i]からKを引いておくと、「算術平均がK以上」→「総和が非負」に言い換えられます。

累積和を使うと各区間が定数時間で求まるので、O(N²)で解くことが出来ますが、今回はO(NlogN)まで速くしないといけません。自分はここまででした。

b[i]=(a[0]+a[1]+…+a[i-1])-K*(i-1)とすると、b[i](0≦i≦N+1)がバラバラの値として存在していて、b[r]-b[l]≧0となるl,r(l<r)の数を求めるのが問題でした。rを左から順に見ていくとして、b[0],b[1],…,b[r-1]の中にb[r]以下の数がいくつあるかが分かれば問題が解けます。BITを使えばこれがO(logN)で求まるのですが、数が大きすぎるので、座標圧縮の要領でb[i]が何番目に大きいのかを求めたc[i]でBITをすればOKです。c[i]は0～N+1であることが保証されており、後はc[i]以下の数の個数をBITで求めて加え、BITにc[i]を追加する、ということを繰り返します。

BITはyukicoderのこの問題が似ている気がしたので載せておきます。練習用にどうぞ。

http://yukicoder.me/problems/no/59

以下解答プログラムです。結局O(NlogN)まで縮められました。

http://arc075.contest.atcoder.jp/submissions/1330330