こんなん、愚直に見ていくしか方法が無さそうだが、愚直に見ていくと $O(N^2M)$ かかる。
(C++などではそれで間に合っちゃうらしいが)
一致する“個数”でなく“偶奇”だけがわかればよいことから、bitsetのxorを用いて定数倍を軽くする方法が考えられる。
「2 列目の値が 3 であるような行は、$i=0,3,4$ 行目」といったように、 $(j,A_{i,j})$ の組毎に、合致する $i$ の集合を持たせたデータを考える。
ある列 $j$ で同じ集合に属する行は、互いに $j$ 列目で値が一致していることになる。
ある行 $i$ について、自身と似ている行を探すには、
j 0 1 2 3 4 i 0 1 2 3 4 5 1 1 2 4 4 5 2 2 1 4 3 5 3 5 4 3 2 1 4 2 1 3 4 5 i=4 について j,A iの集合(自身以外) 43210 (0,2) 00100 (1,1) 00100 (2,3) 01001 (3,4) 00011 (4,5) 00111 ------------- xor 01101
このように、着目中の行の各 $(j,A_{i,j})$ に対する $i$ の集合をxorすると、最後に“1”が立っているものが「似ている」列となる。
実際は、$i \lt j$ のペアのみ探すので、$i$ が小さい方から順に、求解→$i$ の集合への登録、を処理していくと重複を除ける。
(自身を $j$ として、自身より小さい $i$ に限定したペアを求める)
$A$ の制約範囲が狭めなので、$(j,A)$ は高々 $2 \times 10^6$ 通りしか取り得ず、 それぞれに $N$ bitのbitsetを持たせても、$\dfrac{4 \times 10^9}{64} \simeq 6.25 \times 10^7$ でメモリ的には大丈夫。
計算量も、$N$ 個の行に付き、$M$ 回、$\dfrac{N}{64}$ サイズのxor演算を行うため、 総合して $\dfrac{N^2M}{64} \simeq 1.25 \times 10^8$ となり、遅い言語では厳しめだが、なんとか間に合う。
PyPyってたまに、わずかな違いで実行速度に差が生じることがある。
上手にコンパイルしてくれる書き方があるのだろうけど、根本的な要因がわからない。
利用するテクニックも難しめだし、この問題がそれを利用できることに気付くのもなかなか難しい。
(類題を見たことあれば「あ、」と気付くものかもしれない)
最小費用流で解けるかと思ったが、引く数が「選んだindexの $B_i$ の最小値」ならいけるが、最大値なのでダメだった。
まず、$(A_i,B_i)$ を $B_i$ を基準にソートする。
こうすると、引く数は「選んだ中で最も右の $B_i$ を使う」と確定するので考えやすくなる。
以下のDPを定義して分割統治をする。
初期値として、区間の長さが1の時、$dp[l,l+1,1]=A_l-B_l$ である。
ここから、区間を統合して倍の長さの区間の答えを求める、ということを繰り返して、$dp[0,N,k]$ の答えを求めたい。
(2の冪からはみ出す分は、$A_i=-\infty$、$B_i=\infty$ などで埋めておけばよい)
i 0 1 2 3 4 5 6 7 A 3 -1 4 1 -5 9 2 -∞ B -5 -2 -2 0 1 4 8 ∞ dp 8 1 6 1 -6 5 -6 -∞ ←長さ1の区間 dp[i,i+1,1] = Ai-Bi |----||----||----||----| |----------||----------| 区間を倍々にして dp[l,r,*] を求めていく |----------------------|
$[l,m)$ と $[m,r)$ を統合して $dp[l,r,k]$ を求めるにあたり、$[l,m)$ の方から $s$ 個、取ることにすると、
$s=0,1,...,k$ を試して、この中の最大値が、$dp[l,r,k]$ となる。
当然、これを $k$ ごとにやっていたら、$k$ は $0,1,...,r-l$ に付いて求めるため、$O((r-l)^2)$ かかる。
分割統治全体では、$r-l$ が $N$ 以上になるまで、$2^2$ が $N/2$ 回、$4^2$ が $N/4$ 回、、、と繰り返されるため、
$O(N^2)$ かかることになる。
$dp[l,r,*]$ を求めるのは、最大値の畳み込みに相当する。
要は、2つの数列 $X,Y$ で、$X_s$ を左区間(区間内の $A_i$ の大きい方から $s=0,1,...$ 個取ったもの)、$Y_t$ を右区間($dp[m,r,t]$)としたときに、
となる数列 $Z$ を求められれば、$dp[l,r,*]$ が一気に求まる。
この畳み込みは、普通は $O(|X||Y|)$ かかるが、 $X,Y$ のいずれかが上に凸である場合、$O(|X|+|Y|\log|X|)$ などで求める方法がある。
今回の場合、左区間の $X_s$ が「大きい方からの累積和」ということで上に凸であるため、この高速化手法を適用できる。
これを使ってdpを倍々に統合していくと、全体で $O(N \log N)$ で求まる。