Codeforces Round 1032 (Div. 3)

　Fまで六完。Div. 3で二問解けないのはまずい。

コンテストへのリンク

コンテスト後のツイート

D 1から順に運ぶ。
E x桁より上の桁が、1差か0差か、それ以外か
F xより大きいものを含まない区間に分ける。それぞれについて、累積和を取り各値を取るindexをdict(list)でもつ。[l:r]について考えるなら、lは、累積和がS[r]-sで、rの前のxを取るようなindex以前のもの。この個数は二分探索で求まる。

— titia (@titia_til) June 17, 2025

G. Gangsta

　解説AC。典型かもしれないけど難しく感じた。

　まず、0と1の個数のうち多い方、というのを

・((0の個数)+(1の個数)+(0の個数と1の個数の差))/2

　と言い換える。

　そうすると、あとは、全ての区間について、(0の個数と1の個数の差)の総和を求めれば良い。

　このために、"1"を+1、"0"を-1とした累積和を考える。この、任意の二項の差の絶対値を求めれば良い。

　ここでBITを使って、BITに個数や総和を載せて解く方法もあるようだ（よく分かっていない）。

　が、公式解説はもっと簡単。

　累積和の配列をAとし、Aをソートする。

　二項の差の絶対値を考えるということは、自分より大きい項からは引かれ、小さい項については足されるということ。

なので、

・A[i]*(i-(len(A)-1-i))

　の和を求めれば良い。

　前半も後半も見たことあるような内容ではあるが、とはいえこの二つを繋げるのは結構難しい気がする。