Toyota Programming Contest 2024#4（AtCoder Beginner Contest 348）F,G問題メモ

Toyota Programming Contest 2024#4（AtCoder Beginner Contest 348）

F - Oddly Similar

• $N \times M$ の行列 $A$ が与えられる
• $A$ の $i$ 行目と $j$ 行目は、「$A_{i,k}=A_{j,k}$ となる $k$（$1 \le k \le M$）」の個数が奇数の時、「似ている」という
• 似ている行のペア $(i,j)$（ただし $i \lt j$）の個数を求めよ
• $1 \le N,M \le 2000$
• $1 \le A_{i,j} \le 999$

こんなん、愚直に見ていくしか方法が無さそうだが、愚直に見ていくと $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$ となり、遅い言語では厳しめだが、なんとか間に合う。

Python3

PyPyってたまに、わずかな違いで実行速度に差が生じることがある。
上手にコンパイルしてくれる書き方があるのだろうけど、根本的な要因がわからない。

• https://atcoder.jp/contests/abc348/submissions/52241814 j→i の順にイテレート: AC, 1405s
• https://atcoder.jp/contests/abc348/submissions/52241793 i→j の順にイテレート: TLE

G - Max (Sum - Max)

• 長さ $N$ の2つの整数列 $A,B$ が与えられる
• $k=1,2,...,N$ について、以下に答えよ
  • $I=\{1,2,...,N\}$ から $k$ 個選ぶ
  • 「選んだindexの $A_i$ の和」-「選んだindexの $B_i$ の最大値」の最大値を求めよ
• $1 \le N \le 2 \times 10^5$

利用するテクニックも難しめだし、この問題がそれを利用できることに気付くのもなかなか難しい。
（類題を見たことあれば「あ、」と気付くものかもしれない）

最小費用流で解けるかと思ったが、引く数が「選んだindexの $B_i$ の最小値」ならいけるが、最大値なのでダメだった。

まず、$(A_i,B_i)$ を $B_i$ を基準にソートする。
こうすると、引く数は「選んだ中で最も右の $B_i$ を使う」と確定するので考えやすくなる。

以下のDPを定義して分割統治をする。

• $dp[l,r,k]=$ 区間 $[l,r)$ から $k$ 個選んだときの最大値

初期値として、区間の長さが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 \lt k$ のとき
  • $[l,m)$ の方からは、$B_i$ を気にする必要は無いので、$A_i$ の大きい方から $s$ 個、貪欲にとった総和としてよい
  • $[m,r)$ の方からは、$dp[m,r,k-s]$ が達成できる
  • この両区間の和が達成できる
• $s = k$ のとき
  • 右からは取らないので、$dp[l,m,k]$ となる

$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_k=\max_{s+t=k}X_s+Y_t$

となる数列 $Z$ を求められれば、$dp[l,r,*]$ が一気に求まる。

この畳み込みは、普通は $O(|X||Y|)$ かかるが、 $X,Y$ のいずれかが上に凸である場合、$O(|X|+|Y|\log|X|)$ などで求める方法がある。

今回の場合、左区間の $X_s$ が「大きい方からの累積和」ということで上に凸であるため、この高速化手法を適用できる。

• Monotone Minima と SMAWK

これを使ってdpを倍々に統合していくと、全体で $O(N \log N)$ で求まる。

Python3