AtCoder Regular Contest 075 E. Meaningful Mean

以下のことを考えて、やっぱり解説を書くことにした

• 復習のときに思いつかなかったので、ちゃんと記憶に残すために書いておくべき
  • 自分用のメモは残したりしているけど、人に読んでもらうために文章を考えることは、記憶に残す上でも文章を書く練習上でも重要だと思う
• どうせnim-langで解いているからコード貼ってもわからないでしょ、みたいなのが解説を書かない言い訳になっている状況は良くない

問題

E: Meaningful Mean - AtCoder Regular Contest 075 | AtCoder

解法

半開区間の平均について考えると、それがK以上になるのはの区間和が以上になるということである。
これは、もとの数列の各値からKを引いた数列のの区間和が0以上になることと同値なので、その数列において区間和が0以上になるような区間の総数を求めればよい。
数列の半開区間の和が0以上になることは、数列の累積和を取った数列Sにおいて、S[i] <= S[j] となることである。これは数列の転倒数を求める際の方法と似たような方法(Binary Indexed Tree(Fenwick Tree)を用いる方法)で求めることができる。(転倒数の求め方は蟻本中級編3-3 pp.162~163を参照)
具体的には、(S[i], i)を降順ソートして大きい方から順番に見ていき、(S[i], i)のときには、Fenwick Treeのi番目以上の和を求めて、iのところに1をたてることを繰り返せばよい。

計算量

O(NlogN)

コード

以下のコードでは解説と同じように、元の数列の累積和の列S'に対して、(S'[i]-i*K, i)という列を昇順ソートしているが、上記のように元の数列からK引いた列を初めから考えた方が分かりやすいと思う。

感想

• ある区間の平均がK以上を考えるときは、Kを予め引いた列を考えればよいということは、意識していないと僕には思いつけないので知っておく
• 平均の最大を二分探索で求めるやつ(蟻本中級編pp.132-134)に形は似てるけど解き方はかなり違う
  • まあ今回はペアを全て数え上げる問題なので最大値を求める問題とは性質が少し違うし、平均の最大値の方が問題としては難しい気がする

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?