Xmas Contest 2020 I: Implement Me 解説

Xmas Contest 2020

https://atcoder.jp/contests/xmascon20/tasks/xmascon20_i

問題概要

F(x_0, \ldots, x_{M-1}) は， x_0, \ldots, x_{M-1} のうち 1 が L 個以上なら 0 で， L 個未満なら 1 である．この F だけを使って与えられた関数 G\colon \{0, 1\}^N \to \{0, 1\} が作れるか判定し，作れる場合は実装せよ．

簡単な場合

部分点が N \le 2 についています．この部分点自体は 2^{2^N} 通りのうち作れる関数をすべて探索することで獲得できるのですが， M や N が小さい場合について考察してみましょう．

M = 1 のときは F は NOT です F(x_0) = \overline{x_0}．このときは G の入力の変数 y_i いずれかの否定 \overline{y_i} とそのまま \overline{\overline{y_i}} = y_i 以外はどうがんばっても作れません．実はこの場合はコーナーケースであることが後々発覚するので場合分けします．

M = 2 のときは， L = 1 ならサンプルにあるように F は NOR， L = 2 なら F は NAND になっています．リンク先 Wikipedia にもありますが，NOR や NAND はそれ 1 つで任意のブール関数を作れる (完全である) ことがよく知られています．具体的には，NOR の場合は \overline{x} = (x \mathbin{\mathrm{NOR}} x)， (x_0 \mathbin{\mathrm{OR}} x_1) = \overline{x_0 \mathbin{\mathrm{NOR}} x_1}， (x_0 \mathbin{\mathrm{AND}} x_1) = (\overline{x_0} \mathbin{\mathrm{NOR}} \overline{x_1}) のように NOT, OR, AND が，適当な変数をとって 0 = (y_i \mathbin{\mathrm{NOR}} \overline{y_i})， 1 = \overline{0} によって定数が得られて (NAND の場合も同様)， G(y_0, \ldots, y_{N-1}) = \bigvee_{(y'_0, \ldots, y'_{N-1}) \in G^{-1}(1)} \bigwedge_{i=0}^{N-1} [y_i = y'_i] のように書くと G も作れることがわかります (例えばサンプルの場合は (y_0 \mathbin{\mathrm{AND}} \overline{y_1} \mathbin{\mathrm{AND}} y_2) \mathbin{\mathrm{OR}} (y_0 \mathbin{\mathrm{AND}} y_1 \mathbin{\mathrm{AND}} y_2) とします)．

一方， N = 1 のときは，とりあえず最初にできることは F(y_0, \ldots, y_0) しかなくてこれは \overline{y_0} です．次にできるのは y_0 と \overline{y_0} を何個かずつ入れることですが，片方だけ L 個以上だと y_0 か \overline{y_0} になってしまうので意味なく，「両方を L 個以上」または「両方を L 個未満」にすることで定数 0 または 1 が得られます (片方を得ればもう片方も得られます)．が，これは ( M が奇数で) L = \frac{M+1}{2} のときだけできません！　これが特殊な場合になることがわかります． N = 1 だとこれ以上どうすることもできません．

考察

上の考察を合わせる感じにすると， 2 個の値 x, x' を適切な個数選んで入れれば便利なものが作れそうです．具体的には，

  • L \lt \frac{M+1}{2} のときは， L \le \left\lfloor\frac{M}{2}\right\rfloor なので，例えば x を \left\lfloor\frac{M}{2}\right\rfloor 個， x' を \left\lceil\frac{M}{2}\right\rceil 個とすると，両方 L 個以上なので F(x, \ldots, x, x', \ldots, x') = (x \mathbin{\mathrm{NOR}} x')，
  • L \gt \frac{M+1}{2} のときは， L \gt \left\lceil\frac{M}{2}\right\rceil なので，例えば x を \left\lfloor\frac{M}{2}\right\rfloor 個， x' を \left\lceil\frac{M}{2}\right\rceil 個とすると，両方 L 個未満なので F(x, \ldots, x, x', \ldots, x') = (x \mathbin{\mathrm{NAND}} x')

となります．あとはこれを使って M = 2 の考察に書いたように任意のブール関数が実現できます．NOT, OR, AND をとるのに定数回の F の使用がかかるので，全体で F を O(2^N N) 回使うことになります．これで 10^4 行制限は多少の無駄があっても大丈夫だと思いますが， F の使用を O(2^N) 回にすることも一応できます：各 k = 0, \ldots, N と (y'_0, \ldots, y'_{k-1}) \in \{0, 1\}^k に対し \bigwedge_{i=0}^{k-1} [y_i = y'_i] を順に求めていけばよいです (論理決定の二分木を根のほうから作っていくイメージ)．

特殊な場合

さてコーナーケースということにしていた L = \frac{M+1}{2} のときですが，これがこの問題の難しいところです．入力の変数いずれかの否定 F(y_i, \ldots, y_i) = \overline{y_i} かそのまま \overline{\overline{y_i}} = y_i はとりあえず作れて， N \le 2 のときは実はこれ以外は作れないことが以降の議論でわかります．これを予想して実装すると 20 点の部分点となります．

では， G が作れるための必要条件を考えましょう． x_0, \ldots, x_{M-1} のうち 1 が \frac{M+1}{2} 個以上というのは， 0 が M - \frac{M+1}{2} = \frac{M-1}{2} 個以下，すなわち \frac{M+1}{2} 個未満であることと同値です．この対称性に着目すると， F(\overline{x_0}, \ldots, \overline{x_{M-1}}) = \overline{F(x_0, \ldots, x_{M-1})} であることがわかります．つまり，入力の変数の 0/1 をすべて反転させると出力も反転するということです．この性質は F だけを使って作れるすべての関数に伝搬するので， G(\overline{y_0}, \ldots, \overline{y_{N-1}}) = \overline{G(y_0, \ldots, y_{N-1})} が必要条件となることがわかりました．

そして，この条件を満たす G はなんとすべて作ることができます．( N \ge 1 なので，) G(\overline{y_0}, \ldots, \overline{y_{N-2}}, 1) = \overline{G(\overline{y_0}, \ldots, \overline{y_{N-2}}, 0)} が成り立つため， y_{N-1} = 0 のときに正しく G を計算する関数が F だけで作れていれば， y_{N-1} = 1 のときも自動的に正しいということになります (!)．ということは， y_{N-1} が定数 0 だと思って構成してよいということになります (!!)．

定数 0 を得てしまえばあとはいろいろな方法があって，例えば F を F(x_0, \ldots, x_{M-2}, 0) のようにすると M が 1 小さい場合に帰着されて，特殊な場合ではなくなり (ここが M = 1 を最初に処理した理由です)， y_0, \ldots, y_{N-2} のすべての関数を作ることができます．

背景

Post's lattice というものがあります．この束の各元は，合成 (と射影) について閉じたブール関数の集合，別の言い方をすれば「組み合わせて作った関数にも伝搬する性質」を表しています．このなかでも最大元 \top を除いたときの極大元 M, D, A, P_0, P_1 が重要で，これは (この問題の形に限らない) ブール関数 F\colon \{0, 1\}^M \to \{0, 1\} についての以下の性質をそれぞれ表します：

  • M (monotone)： x_0 \le x'_0,\, \ldots,\, x_{M-1} \le x'_{M-1} ならば F(x_0, \ldots, x_{M-1}) \le F(x'_0, \ldots, x'_{M-1})
  • D (self-dual)： F(\overline{x_0}, \ldots, \overline{x_{M-1}}) = \overline{F(x_0, \ldots, x_{M-1})}
  • A (affine)：ある a_0, \ldots, a_{M-1}, b \in \{0, 1\} が存在して， F(x_0, \ldots, x_{M-1}) \equiv a_0 x_0 + \cdots + a_{M-1} x_{M-1} + b \pmod{2}
  • P_0 ( 0-preserving)： F(0, \ldots, 0) = 0
  • P_1 ( 1-preserving)： F(1, \ldots, 1) = 1

つまり， F がこれらのいずれかの性質を持っていたら F から作れる関数もその性質を持ち，一方 F がこれらのいずれをも持っていなかったら F だけですべてのブール関数が作れる，ということが知られています．

今回の問題では， M \ge 2 として， L = \frac{M+1}{2} のときは F が D に属すが M, A, P_0, P_1 に属さないので D に属するすべての関数が作れて，そうでないときは F が M, D, A, P_0, P_1 のいずれにも属さないのですべての関数が作れる，ということになります．わたしは不勉強で Post's lattice の導出を知らないのですが，束の構造の証明から具体的な構成方法も得られるのかもしれません (ご存じの方は教えてください！)．

統計情報

正解者：tomerun さん (2:45:27) はじめ 2 チーム

コメント

majority 関数を想像しつつ monotone でなくなるように適当に変えてみました．すべてのブール関数が作れるかの判定法を知っていたのでずるではあるのですが，構成方法を思いついてみると L = \frac{M+1}{2} の場合がとても面白かったので問題になりました．構築問題としても見慣れない雰囲気があって (ありますよね？)，なんだか騙されたような感じがしますね．