O(N * log(max(a))解法
解法の軸は解説の通りですが、いくらかの工夫をします。まず、数列のソートに桁ごとのバケットソートを使用します。下位の桁から順に計算していけば基数ソートの動きそのままになるので、各桁で O(N) でソートが可能です。数列 a, b 双方をこれでソートしておくことで二分探索パートに尺取りを使えるようになり、こちらも O(N) に抑えることが出来ます。よって全体で O(N * log(max(a))) になります。
本番では想定解法にすら辿り着けませんでしたが、２つの部分それぞれで log を落とす美しい解法だと思います。*1
Submission #2424985 - AtCoder Beginner Contest 091
WaveletMatrixで解く
こちらを見て、実装パートを WaveletMatrix でショートカット出来ることを知りました*2。自分の実装でやってみたところ、ぎりぎりTLE回避できたので載せます。やはり WaveletMatrix は強いと感じました。
Submission #2425330 - AtCoder Beginner Contest 091
私が現状使用しているライブラリ*3も貼っておきます(宣伝)
