ABC348 F - Oddly Similar

https://atcoder.jp/contests/abc348/tasks/abc348_f (opens in a new tab)
青色上位。bit 並列化。

まず前提として次のテクニックを知っている必要がある。

あるものの個数の偶奇を問われる問題はわざわざカウントする必要はなく、適宜 xor を取るだけで良い
```
cnt = 0
for e in iterable:
    if f(e):
        cnt ^= 1
if cnt == 1:
    print('Oddly!')
```

各数列 $A_i, A_j$ を個別にチェックすると TLE になるのは目に見えているので（高速な言語ではそうでもない (opens in a new tab)らしい）、数列の各要素同士（インデックス同じもの）をまとめて計算することを試みるのは自然な発想である。

つまり、 $k=1,\ldots,m$ に対して、各 $A_{i,k},A_{j,k}$ が等しいものをチェックできないかと考えるわけだが、ナイーブに行うと $\mathcal{O}(N^2)$ かかるため、結局総じて $\mathcal{O}(N^2M)$ となり間に合わない。

ここで、 $k=1,\ldots,m$ の各ステップで、 $A_{i,k},A_{j,k}$ が等しくなるとき 1 になるような $n\times{n}$ の表を作成することにする。

例えば入力例 1 において、

$k=1$ の時、 $A_{1,1}=1,A_{2,1}=1,A_{3,1}=2$ により、 $A_{1,1}=A_{1,1},A_{1,1}=A_{2,1},A_{2,1}=A_{2,1},A_{2,1}=A_{2,2},A_{3,1}=A_{3,1}$ により表は次の通りになる。

$k=1$
i\j 1 2 3
1 1 1 0
2 1 1 0
3 0 0 1

i\j	1	2	3
1	1	1	0
2	1	1	0
3	0	0	1

同様にして、 $k=2,3$ の時の表はそれぞれ、

$k=2$

i\j 1 2 3
1 1 0 0
2 0 1 1
3 0 1 1
$k=3$

i\j 1 2 3
1 1 0 0
2 0 1 1
3 0 1 1

i\j	1	2	3
1	1	0	0
2	0	1	1
3	0	1	1

i\j	1	2	3
1	1	0	0
2	0	1	1
3	0	1	1

となる。最終的にこれらの表を足し合わせれば、 $i,j$ 要素が $A_i$ と $A_j$ について、 $A_{i,k}=A_{j,k}$ となる $k$ の個数を表すため、そこから値が奇数となるものの個数をカウントすることで問題に回答することができるが、実際のところ、前述のテクニックの利用により、表同士の排他的論理和を取ることで同じ解を得ることができる。

ここで、行同士の計算は独立に計算できることに注意する。

さて、表を眺めると、 $A_{i,k}=A_{j,k}$ として同じ値を持つインデックス $i,j$ は表においても行 $i,j$ （あるいは列 $i,j$ ）が等しくなるため、 $A_{i,k}$ の値が等しいものをまとめて計算することができる。さらに、この表の各行を bit で管理する、つまり $A_{i,k}=A_{j,k}=x$ となる時、 $k,x$ に対して $i$ 番目と $j$ 番目が立つような bit を用意すれば、次の排他的論理和による計算も高速化することができる。

提出コード

# -*- coding: utf-8 -*-
 
 
n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
 
# mat[i] := mat[i] & 1 << j == 1 であれば A_i と A_j は似ている
mat = [0] * n
 
for k in range(m):
    # bits[x] := sum(1 << i for i in A_{i,k} = x)
    bits = [0] * 1000
    for i in range(n):
        bits[a[i][k]] |= 1 << i
    for i in range(n):
        mat[i] ^= bits[a[i][k]]
 
ans = 0
 
for i in range(n):
    for j in range(i + 1, n):
        if mat[i] & (1 << j):
            ans += 1
 
print(ans)

Python (PyPy 3.10-v7.3.12), 1508 ms (opens in a new tab)