くふむ

けふぇめ

WBC004 B - Linear Code 解説

WBC

2021年3月18日に開かれたウインドベル(@Twi_Stamp)主催の競プロ有志コンテストWind Bel Contest 004 – Good Bye 2A Day 2の解説です。

問題文

線形符号を構成する長さ L の符号語 C_1,C_2,\cdots,C_N が与えられるので、異なる 2 つの符号語間のハミング距離の最小値を求めてください。

線形符号
同じ長さのビット列の集合を A として、任意の a,b\in A について a\ \mathrm{XOR}\ b\in A を満たすとき A を線形符号とする。

制約

  • 2 \leq N \leq 2^{10} (部分点100点)
  • 2 \leq N \leq 2^{16}
  • N は整数
  • C_i は0と1からなる文字列
  • C_i はすべて異なる
  • 1 \leq L \leq 63

解説 (部分点)

そもそも「ハミング距離」とは何でしょうか。Wikipediaの解説を見てみましょう。

ハミング距離（ハミングきょり、英: Hamming distance）とは、等しい文字数を持つ二つの文字列の中で、対応する位置にある異なった文字の個数である。

ハミング距離の例： 1011101 と 1001001 の間のハミング距離は 2 である。

ハミング距離 - Wikipedia

要するに、同じ位置にある違う文字の個数がハミング距離なのですね。

問題文はハミング距離の最小値を求めろと言っているので、言われた通りに与えられたビット列の全ペアについてハミング距離を計算して、その最小値を答えとすればよいです。

計算量は \mathrm{O}(N^{2}) 通りのペアに対して \mathrm{O}(L) で文字を一つ一つ見比べてハミング距離を求めるので、全体で \mathrm{O}(N^{2}L) になります。部分点の制約は N \leq 2^{10} \approx 10^{3}, L \leq 63 なので、十分間に合います。

実装例 (部分点)

INF = float("inf")

def solve():
    # input
    n, l = map(int, input().split())
    c = [input() for _ in range(n)]

    # 答えを十分大きい値で初期化
    ans = INF

    # 異なるi, jの組に対して
    for i in range(n):
        for j in range(i):
            # ハミング距離を求める
            cnt = 0
            for k in range(l):
                if c[i][k] != c[j][k]:
                    cnt += 1
            # 暫定の答えより小さければ更新
            if ans > cnt:
                ans = cnt
    
    # output
    print(ans)

t = int(input())
for _ in range(t): solve()

これで部分点 100 点をゲットできます。

解説

結論から述べると、線形符号のハミング距離の最小値は、\mathbf{0} 以外のビット列のpopcountの最小値に一致します。 どのようにしてこの結論に至るのか考えてみましょう。

上で書いた愚直解から計算量を落としていきましょう。i, jの2重ループを何とかするのは現段階では難しそうなので、まずはハミング距離を効率的に求める方法を模索するところから始めます。ハミング距離とは、同じ位置にある違う文字の個数でした。これだけでは文字を全部見比べることしかできないように思えます。

しかし、今回は見比べたい文字が \mathbf{2} 進数という重要な制約があります。2 進数のもとで異なる文字を探すなら、ビット演算が役に立ちそうですね？

……そうです！ まさに \mathrm{\mathbf{XOR}} が、ビット列間の異なる文字を求める演算なのです！

2進数のハミング距離
ビット列 a と b の異なる部分は a\ \mathrm{XOR}\ b で求められる。 よって、ビット列 a と b のハミング距離は、 a\ \mathrm{XOR}\ b のpopcount ( 2 進数で表したときの 1 の個数) に一致する。

したがって、この問題は次の問題に帰着できます。

線形符号を構成する長さ L の符号語 C_1,C_2,\cdots,C_N が与えられるので、異なる 2 つの符号語間の \mathrm{\mathbf{XOR}} のpopcountの最小値 を求めてください。

まだ計算量は落ちていませんが、 \mathrm{XOR} の演算で表せると嬉しい気分になることがあります。ここで線形符号の定義をもう一度見てみましょう。

線形符号
同じ長さのビット列の集合を A として、任意の a,b\in A について a\ \mathrm{XOR}\ b\in A を満たすとき A を線形符号とする。

ここにもドンピシャで \mathrm{XOR} が出てきています！

”任意の a,b\in A について a\ \mathrm{XOR}\ b\in A を満たす” ことから、先程帰着された問題の「異なる 2 つの符号語間の \mathrm{\mathbf{XOR}} 」は、すべて「 C_1,C_2,\cdots,C_N 」に入っていることになります。

よって、 C_1,C_2,\cdots,C_N のpopcountの最小値を求めれば、それが答えです……と言いたいところですが、それは嘘で、 0 が含まれていると、 0 のpopcountは 0 なので最小値が 0 になって終了してしまいます。

というのも、「異なる 2 つの符号語間の \mathrm{XOR} 」が 0 になることはないのです。そもそも \mathrm{XOR} の性質から a\ \mathrm{XOR}\ b = 0 となるのは a=b のときだけですが、”集合内の異なる 2 つの符号語間” なので a=b とはならず、 \mathrm{XOR} によって 0 が出てくることはありません。

逆に、 C_1,C_2,\cdots,C_N のうち 0 以外の要素は全て出てきます。 a\ \mathrm{XOR}\ 0 = a だからです。

以上より、元の問題は以下の問題に帰着することができました。この問題は計算量 \mathrm{O}(NL) で解くことができます。

線形符号を構成する長さ L の符号語 C_1,C_2,\cdots,C_N が与えられるので、C_1,C_2,\cdots,C_N のうち 0 以外の要素のpopcountの最小値 を求めてください。

実装例

def solve():
    n, l = map(int, input().split())
    print(min(filter(lambda x: x > 0, (input().count("1") for _ in range(n)))))

t = int(input())
for _ in range(t): solve()

ひとこと

Testerとして解けなかった問題三銃士の一角です。最初は部分点なんてなかったのですが、Bにこれが置かれてるのやばいだろと思って愚直解が通るような部分点を設置してもらうよう申し立てたという裏話があります。