2019年4月4日木曜日

ARC 075 E - Meaningful Mean

ARC 075 E - Meaningful Mean

ai=ai+1Ka'_i = a_{i+1}-Kと0-basedに直してKKを引き、Sk=a0+a1+...+ak1S_k = a'_0 + a'_1 + ... + a'_{k-1}と累積和を定めると、与えられた問題はl<rl < rかつSlSrS_l \le S_rであるような(l,r){0,...,N}2(l, r) \in \{ 0, ..., N \}^2の総数を求めることに帰着する。この数は数列(Sk)(S_k)の転倒数IIについてN(N+1)/2IN(N+1)/2 - Iであると見ることもできるし、あるいはこれ自体を転倒数と同じように数えることもできる。

Treap、座標圧縮してBIT、マージソートの3つで通した。コンパイル時間を除くとそれぞれ250ms、100ms、60msくらいだった。BITが最速でないのを一瞬だけ意外に思ってしまったが、BITを使う前にソートするのだから単にソートするだけより遅いのは自明だった。

マージソートの高速化

マージソートで転倒数を求める時に、配列を分割していって特定のサイズ以下になったらバブルソートに切り替えるという方針が気になっていたので試してみたが、大した効果はないようだった。(長さ8以下の時にバブルソートに切り替えると3%くらいは速くなってるかも。)

→よく考えたら、挿入ソートでも転倒数を計算できるし、平均的にはそちらのほうが速いはずだ。長さ20以下のときに挿入ソートに切り替えてみたら10%くらい速くなった。

あとは再帰をやめてボトムアップにしたらどのくらい速くなるか……とか?1 in-placeで計算する方法とかそういうのも一応は気になる。競プロで役立つことはなさそうだけど……


  1. でも、長さ16以下で挿入ソートに切り替えれば、再帰呼び出しが9割くらい減ってる計算なのであまり意味がない気がする。 ↩︎