Xmas Contest 2018 E: Exclusive☆OR 解説

https://atcoder.jp/contests/xmascon18/tasks/xmascon18_e

問題概要

$N$ 個のブール変数から $2$ 個とった XOR たちを，AND と OR と NOT を使って作る．NOT の使用回数を最小化せよ．

N = 1 のとき

何もしなければ正解です．

N = 2 のとき

$b_0 \oplus b_1 = (b_0 \vee b_1) \wedge \overline{(b_0 \wedge b_1)}$ なので， $b_0 \wedge b_1$ に NOT を使うと $1$ 回でできます．NOT なしでは $b_0 \wedge b_1$ と $b_0 \vee b_1$ しか作れないので， $0$ 回ではできません．

N = 3 のとき

NOT $2$ 回でできます．下からの評価 ( $1$ 回ではできない) は後ほど．

$N = 3$ の場合はこちらで手で遊べる．

と書いてあるやつで遊んでみると解けるかもしれません．正解できる NOT 対象はいくつかあるのですが，次の方法が一般の $N$ での解法に繋がります：

$\begin{align} f(1, 2, 3) &= b_0 \vee b_1 \vee b_2, \\ f(2, 3) &= (b_0 \wedge b_1) \vee (b_0 \wedge b_2) \vee (b_1 \wedge b_2), \\ f(3) &= b_0 \wedge b_1 \wedge b_2, \\ f(1) &= \overline{f(2, 3)} \wedge f(1, 2, 3), \\ f(2) &= \overline{f(3)} \wedge f(2, 3), \\ b_0 \oplus b_1 &= (b_0 \vee b_1) \wedge (f(1) \vee (b_2 \wedge f(2))). \end{align}$

$f(x_1, \ldots, x_m)$ は「 $b_0, \ldots, b_{N-1}$ のうち true のものの個数が $x_1, \ldots, x_m$ のいずれかである」かどうかを表すブール変数になっています．この変数に着目することが以下の解法での鍵となってきます．

N - 1 回解法

次の $3$ ステップでできます：

$f(1, \ldots, N), f(2, \ldots, N), \ldots, f(N-1, N), f(N)$ を求める．これは AND と OR だけでできる．
$f(1), f(2), \ldots, f(N-1)$ を求める． $f(x) = \overline{f(x+1, \ldots, N)} \wedge f(x, \ldots, N)$ である．ここで $N - 1$ 回の NOT を使っている．
$b_i \oplus b_j$ を求める．まず， $g_{ij}(x)$ を「 $b_i$ と $b_j$ 以外のうち true が $x - 1$ 個以上」かどうかとする．これは AND と OR だけで求まる．すると，以下が成り立つ：

$\begin{align} b_i \oplus b_j = (b_i \vee b_j) \wedge \bigvee_{x=1}^{N-1} (g_{ij}(x - 1) \wedge f(x)). \end{align}$

最後の式が何を意味しているかというと，「 $b_i$ と $b_j$ のうちには true が $1$ 個以上」かつ「 $b_i$ と $b_j$ 以外には true が $x - 1$ 個以上」かつ「全体では true がちょうど $x$ 個」，というのを $1 \le x \le N - 1$ について OR をとっていますが， $1 + (x - 1) = x$ なので「以上」が消えて，「 $b_i$ と $b_j$ のうちには true がちょうど $1$ 個」，すなわち $b_i \oplus b_j$ がもれなく求められている，ということになります．

log N 回解法

上の解法のステップ $2$ は実は $\lceil \log_2 N \rceil$ 回の NOT でできてしまいます． $N = 8$ のときの例を示すとこんな感じ：

$\begin{align} f(1, 2, 3, 4) &= \overline{f(5, 6, 7, 8)} \wedge f(1, 2, 3, 4, 5, 6, 7, 8), \\ f(3, 4) &= f(1, 2, 3, 4) \wedge f(3, 4, 5, 6, 7, 8), \\ f(3, 4, 7, 8) &= f(3, 4) \vee f(7, 8), \\ f(1, 2, 5, 6) &= \overline{f(3, 4, 7, 8)} \wedge f(1, 2, 3, 4, 5, 6, 7, 8), \\ f(1, 2) &= f(1, 2, 5, 6) \wedge f(1, 2, 3, 4), \\ f(5, 6) &= f(1, 2, 5, 6) \wedge f(5, 6, 7, 8), \\ f(2) &= f(1, 2) \wedge f(2, 3, 4, 5, 6, 7, 8), \\ f(4) &= f(3, 4) \wedge f(4, 5, 6, 7, 8), \\ f(6) &= f(5, 6) \wedge f(6, 7, 8), \\ f(2, 4, 6, 8) &= f(2) \vee f(4) \vee f(6) \vee f(8), \\ f(1, 3, 5, 7) &= \overline{f(2, 4, 6, 8)} \wedge f(1, 2, 3, 4, 5, 6, 7, 8), \\ f(1) &= f(1, 3, 5, 7) \wedge f(1, 2), \\ f(3) &= f(1, 3, 5, 7) \wedge f(3, 4), \\ f(5) &= f(1, 3, 5, 7) \wedge f(5, 6), \\ f(7) &= f(1, 3, 5, 7) \wedge f(7, 8). \end{align}$

一般には， $k = \lceil \log_2 N \rceil, \ldots, 2, 1$ に対して，「下から $k$ ビット目が $1$ である数に $1$ を足したもの」たちが $f$ の中身に入るような変数に NOT をすると上手くいきます．すごい．

行数制限

ここまで NOT の回数だけを気にしていましたが，この問題では AND, OR, NOT を合わせて $10^5$ 回以下でなければいけないのでした．ステップ $1$ とステップ $3$ で「true が $x$ 個以上」みたいなのを求めるのを愚直にやると $N$ について指数回かかってしまいます ( $N \le 10$ くらいまで正解できて， $60$ 点です)．これは，DP で $O(N^2)$ の計算でできます：

for i = 0 to N - 1:
  for x = N - 1 to 1:
     f(x + 1, ..., N) := f(x + 1, ..., N) OR (f(x, ..., N) AND b_i)
  f(1, ..., N) := f(1, ..., N) OR b_i

ステップ $3$ のほうでは $O(N^2)$ 回 ( $b_i$ たちから $2$ 個除いて) これをやるので $O(N^4)$ 回の計算になります．実はこれを $O(N^3 \log N)$ にすることもできますが省略します (満点には必要ないです)．これで無事に $10^5$ 行に収まるようにできました．

下からの評価

NOT の最小使用回数は $\lceil \log_2 N \rceil$ です．これ未満ではできないことを示しておきます．

NOT の使用回数が $t \lt \lceil \log_2 N \rceil$ でできるプログラム $P$ が存在したとします． $P$ の入力に $(b_0, \ldots, b_{N-1}) = (1, 0, 0, \ldots, 0), (1, 1, 0, \ldots, 0), (1, 1, 1, \ldots, 0), \ldots, (1, 1, 1, \ldots, 1)$ の $N$ 通りを入れたとき， $2^t \lt N$ なので鳩ノ巣原理より，どれか $2$ パターンでは $t$ 回の NOT の計算結果が全部一致するはずなのです．それを $(\underbrace{1, \ldots, 1}_i, 0, \ldots, 0)$ と $(\underbrace{1, \ldots, 1}_j, 0, \ldots, 0)$ ( $i \lt j$ ) のときとします．

このとき，以下のようなプログラム $Q$ が作れてしまいます：

$Q$ の入力は $1$ 変数である．入力 $c$ に対して， $P$ に入力 $(\underbrace{1, \ldots, 1}_{i}, \underbrace{c, \ldots, c}_{j-i}, 0, \ldots, 0)$ を与える．
$P$ の計算途中において， $t$ 箇所のNOT を使う部分は，上で計算結果が一致したという値の定数に置き換える．
$P$ の出力 $b_i \oplus b_{i+1}$ をとってきて $Q$ の出力とする．

すると $Q$ の出力は $\overline{c}$ ですが， $Q$ は AND と OR しか使っていないので NOT ができてしまうのは矛盾です．

コンテスト開始後はしばらくジャッジが正常に動いておらず申し訳ありませんでした．

満点までの道のりが壮大な感じで，難しい問題だったと思います．でもなんかすごいですよねこれ．

作題のきっかけは，「3-not problem」 (2 NOTs problem だったり呼称は安定していないっぽい) という一部界隈では有名らしい問題を知ったことです． $N = 3$ で， $\overline{b_0}, \overline{b_1}, \overline{b_2}$ を NOT 2 回で作ろうというもの．一般の $N$ では最小 $\lceil \log_2 (N + 1) \rceil$ 回です． $\overline{b_i}$ たちがあれば XOR は作れるのですが， $N = 2$ を考えたらもう少しうまくできるのではと思い， $N = 4$ を全探索していろいろ気づいた，という流れでありました．

hos.lyric's blog