解法概要

以下のようなもの:

  1. 高次の項を無視する
    • 具体的には、高次の項の係数の総和を \(K\) として \(K x_1 x_2 x_3 \dots x_8\) などの単一の項で置き換える
    • 調整した結果として次数 \(d \ge 8\) を無視
    • 嘘要素はここだけで、以降は厳密に一致する関数を得るような処理
  2. \(2\) 次以下の項はそのまま使う
  3. \(3\) 次以上の負の項は \(\min_w w \cdot (d - 1 - x_1 - x_2 - x_3 - \dots - x_d)\) に還元
  4. \(3\) 次以上の正の項は \(2 - x_1 x_2 + \min _ {w_1} w_1 \cdot (1 - x_1 - x_2 + x_3) + \dots + \min _ {w _ {d - 2}} w _ {d - 2} \cdot (d - 2 - x_1 - x_2 - x_3 - \dots - x _ {d - 1} + x_d)\) に還元
  5. 追加変数を分割することで係数の最大値を低減

探索はしていないので実行時間は \(5\) msほど。

まとめ

A問題は暫定 \(1\) 位だがB問題とC問題はそれぞれ暫定で \(40\) 位と \(31\) 位だった。 高次の項を無視したギャンブル (\(10\%\) でWA) が効いただけという印象を受ける。

問題概要

pseudo-boolean function (PBF) \(f\) が与えられる。 これを quadratic pseudo-boolean function (QPBF) \(g\) でいい感じに近似せよ。

ただし PBF とは整数係数の多項式 \(f \in \mathbb{Z}[x_1, \dots, x_N]\) であって引数に真偽値しか考えないもの \(f : 2^N \to \mathbb{Z}\) のこと。 QPBF とはその項を高々 \(2\) 次に制限したもの。

考察: QPBF に関するもの

前提: \(g(X) = f(X)\) forall \(X\) な \(g\) は簡単に作れる

この \(g\) を直接に焼き鈍しで作ろうとしてはいけません

冪等性

\(x^2 = x\) なので指数は考えなくてよい

否定

\[(\lnot x_1) = \bar{x_1} = 1 - x_1\]

最小値

\[\begin{array}{lll} \min(0, f) & = & \min _ {w \in 2} wf \\ \min(f, g) & = & \min _ {w \in 2} (wf + \bar{w}g) \\ \end{array}\]

負の単項式

  • 新規変数: \(1\)
  • 新規項数: \(d + 1\)
  • 最大係数: \(d - 1\)
\[\begin{array}{lll} - x_1 x_2 x_3 & = & \min(0, 2 - x_1 - x_2 - x_3) \\ & & \min w \cdot (2 - x_1 - x_2 - x_3) \\ - x_1 x_2 x_3 x_4 & = & \min(0, 3 - x_1 - x_2 - x_3 - x_4) \\ & & \min_w w \cdot (3 - x_1 - x_2 - x_3 - x_4) \\ \vdots & & \\ - x_1 x_2 x_3 \dots x_d & = & \min(0, d - 1 - x_1 - x_2 - x_3 - \dots - x_d) \\ & & \min_w w \cdot (d - 1 - x_1 - x_2 - x_3 - \dots - x_d) \\ \end{array}\]

結果は \(x_1, x_2, x_3, \dots, x_d\) の順序に依存しない。

置換

\(w = x_1 x_2\) と見做せる変数 \(w\) を導入したい。 正整数 \(A, B, C\) を適切に選んで式 \(A x_1 x_2 + w \cdot (- B x_1 - B x_2 + C)\) を考えると、以下のようにして \(w\) が設定される。

  • \(x_1 = x_2 = 0\) のときは \(C \gt 0\) なので \(w = 0\)
  • \(x_1 = 1\) かつ \(x_2 = 0\) やその逆のときは \(- 2 + C \gt 0\) なので \(w = 0\)
  • \(x_1 = x_2 = 1\) のときは \(- 2B + C \lt 0\) なので \(w = 1\)

ただし \(w\) を他の場所で利用するとその使い方によっては \(x_1 = x_2 = 1\) であっても \(w = 1\) の場合の方が小さくなる可能性がある。 これは十分大きな整数 \(K\) を用いて \(K \cdot (A x_1 x_2 + w \cdot (- B x_1 - B x_2 + C))\) とすれば解決できる。

正の単項式: 単純な還元

  • 新規変数: \(m_d = d - 2\)
    • \(d = 3, 4, 5, \dots, 10\) のときそれぞれ \(1, 2, 3, 4, 5, 6, 7, 8\)
  • 新規項数: \(\frac{d^2 + 3d - 10}{2}\) (ただし定数項と新規変数を含まない \(1\) 項を除く)
    • \(d = 3, 4, 5, \dots, 10\) のときそれぞれ \(4, 9, 15, 22, 30, 39, 49, 60\)
  • 最大係数: \(c_d = d - 2\)
    • \(d = 3, 4, 5, \dots, 10\) のときそれぞれ \(1, 2, 3, 4, 5, 6, 7, 8\)
\[\begin{array}{lll} x_1 x_2 x_3 & = & 1 - \bar{x_1} - x_1 \bar{x_2} - x_1 x_2 \bar{x_3} \\ & = & 2 - x_1 x_2 - x_1 x_2 \bar{x_3} \\ & = & 2 - x_1 x_2 + \min_w w \cdot (2 - x_1 - x_2 - \bar{x_3}) \\ & = & 2 - x_1 x_2 + \min_w w \cdot (1 - x_1 - x_2 + x_3) \\ x_1 x_2 x_3 x_4 & = & 1 - \bar{x_1} - x_1 \bar{x_2} - x_1 x_2 \bar{x_3} - x_1 x_2 x_3 \bar{x_4} \\ & = & 2 - x_1 x_2 - x_1 x_2 \bar{x_3} - x_1 x_2 x_3 \bar{x_4} \\ & = & 2 - x_1 x_2 + \min _ {w_1} w_1 \cdot (1 - x_1 - x_2 + x_3) + \min _ {w_2} w_2 \cdot (2 - x_1 - x_2 - x_3 + x_4) \\ \dots & & \\ x_1 x_2 x_3 \dots x_d & = & 1 - \bar{x_1} - x_1 \bar{x_2} - x_1 x_2 \bar{x_3} - \dots - x_1 x_2 x_3 \bar{x_d} \\ & = & 2 - x_1 x_2 + \min _ {w_1} w_1 \cdot (1 - x_1 - x_2 + x_3) + \dots + \min _ {w _ {d - 2}} w _ {d - 2} \cdot (d - 2 - x_1 - x_2 - x_3 - \dots - x _ {d - 1} + x_d) \\ \end{array}\]

結果は \(x_1, x_2, x_3, \dots, x_d\) の順序に依存する。 特に \(x_1 x_2\) という項の出現には注意すべき。 次のようにして特殊化をやめることで解決はするが、変数は増える。

\[\begin{array}{lll} x_1 x_2 & = & 1 - \bar{x_1} - x_1 \bar{x_2} \\ & = & x_1 + \min_w w \cdot (1 - x_1 - \bar{x_2}) \\ & = & x_1 + \min_w w \cdot (- x_1 + x_2) \\ \end{array}\]

後の手法との比較のために漸化式の形で書くと、

\[\begin{array}{lll} x_1 x_2 \dots x _ {d-1} x_d & = & x_1 x_2 \dots x _ {d-1} (1 - \bar{x_d}) \\ & = & x_1 x_2 \dots x _ {d-1} - x_1 x_2 \dots x _ {d-1} \bar{x_d} \\ \end{array}\]

正の単項式: higher-order clique reduction

  • 新規変数: \(m_d = \lfloor \frac{d - 1}{2} \rfloor\)
    • \(d = 3, 4, 5, \dots, 10\) のときそれぞれ \(1, 1, 2, 2, 3, 3, 4, 4\)
  • 新規項数: \(l_d = {} _ d C_2 + m_d (1 + d)\)
    • \(d = 3, 4, 5, \dots, 10\) のときそれぞれ \(7, 11, 22, 29, 45, 55, 76, 89\)
  • 最大係数: \(d = 3\) のとき \(1\) かつ \(d \ge 4\) のとき \(4 \lfloor \frac{d}{2} \rfloor - 5\)
    • \(d = 3, 4, 5, \dots, 10\) のときそれぞれ \(1, 3, 3, 7, 7, 11, 11, 15\)

対称式であることを踏まえ

\[\begin{array}{lll} S_1 & = & \sum_i x_i = x_1 + x_2 + \dots + x_d \\ S_2 & = & \sum_i \sum _ {j \lt i} x_i x_j = x_1 x_2 + x_1 x_3 + x_2 x_3 + \dots + x _ {d - 1} x_d \\ \end{array}\]

とおく。このとき

\[\begin{array}{lll} x_1 x_2 x_3 & = & S_2 + \min _ {w_1} w_1 \cdot (1 - S_1) \\ x_1 x_2 x_3 x_4 & = & S_2 + \min _ {w_1} w_1 \cdot (3 - 2 S_1) \\ x_1 x_2 x_3 x_4 x_5 & = & S_2 + \min _ {w_1} w_1 \cdot (3 - 2 S_1) + \min _ {w_2} w_2 \cdot (1 - S_1) \\ x_1 x_2 x_3 x_4 x_5 x_6 & = & S_2 + \min _ {w_1} w_1 \cdot (3 - 2 S_1) + \min _ {w_2} w_2 \cdot (7 - 2 S_1) \\ x_1 x_2 x_3 x_4 x_5 x_6 x_7 & = & S_2 + \min _ {w_1} w_1 \cdot (3 - 2 S_1) + \min _ {w_2} w_2 \cdot (7 - 2 S_1) + \min _ {w_3} w_3 \cdot (5 - S_1) \\ x_1 x_2 x_3 x_4 x_5 x_6 x_7 x_8 & = & S_2 + \min _ {w_1} w_1 \cdot (3 - 2 S_1) + \min _ {w_2} w_2 \cdot (7 - 2 S_1) + \min _ {w_3} w_3 \cdot (11 - 2 S_1) \\ \vdots & & \\ \end{array}\]

一般に \(d\) が奇数のとき、

\[x_1 \cdots x_d = S_2 + \sum _ {i \le m_d - 1} \min _ {w_i} w_i \cdot (4 i - 1 - 2 S_1) + \min _ {w _ {m_d}} w_{m_d} \cdot (2 m_d - 1 - S_1)\]

\(d\) が偶数のとき、

\[x_1 \cdots x_d = S_2 + \sum _ {i \le m_d} \min _ {w_i} w_i \cdot (4 i - 1 - 2 S_1)\]

になる。

単純な還元と違う点としては、変数の並びに依存せず \(x_1 x_2\) のような新規変数を含まない項が \({} _ d C _ 2\) 種類すべて使われること。

splitting of common parts

これは項を潰すのでなく変数を潰すもの。 係数がすべて正の式 \(f = x g\) と常に \(K \ge g\) を満たす \(K\) に対し \(f = g - \min_w w \cdot (K - g)\) とすると正の単項式の次数が落ちる。 正の単項式の単純な還元のちょうど \(1\) 段階だけを複数の項に渡ってまとめて行なうようなイメージである。

例えば \(f = x_1 g = K_1 x_1 x_2 x_3 + K_2 x_1 x_4 x_5 x_6\) があったとする。 ただし係数はすべて正 \(K_1, K_2 \gt 0\) とする。 \(x_1 = 0\) なら \(f = 0\) かつ \(x_1 = 1\) なら \(f = g\) だが、そうなるように新規変数を導入すればよい。 \(K \ge K_1 + K_2\) であるような大きい整数 \(K\) を置く。 このとき \(f _ {x_1} = g - \min(0, K x_1 - g)\) とする。 常に \(K \ge g\) なので \(x_1 = 1\) のとき \(\min(0, K x_1 - g) = 0\) となって \(f _ {x_1} = g\)。 仮定から \(g \ge 0\) なので \(x_1 = 0\) のとき \(\min(0, K x_1 - g) = - g\) となって \(f _ {x_1} = 0\)。 具体的には

\[\begin{array}{lll} f _ {x_1} & = & g - \min(0, K x_1 - g) \\ & = & g - \min_w w \cdot (K x_1 - g) \\ & = & K_1 x_2 x_3 + K_2 x_4 x_5 x_6 + \min _ {w_1} w_1 \cdot (K_1 + K_2 - K_1 x_2 x_3 - K_2 x_4 x_5 x_6) \\ & = & K_1 x_2 x_3 + K_2 x_4 x_5 x_6 + \min _ {w_1} ((K_1 + K_2) w_1 - K_1 w_1 x_2 x_3 - K_2 w_1 x_4 x_5 x_6) \\ & = & K_1 x_2 x_3 + K_2 x_4 x_5 x_6 + \min _ {w_1, w_2, w_3} ((K_1 + K_2) w_1 + K_1 w_2 (2 - w_1 - x_2 - x_3) + K_2 w_3 (3 - w_1 - x_4 - x_5 - x_6)) \\ \end{array}\]

これすごく「微分」とか呼びたいけどそうでないのだろうか。論文読んでないので分からず。

係数の削減

\(K \min_w w f(X ; w)\) という式があるときこれを \(K = K_1 + K_2\) であるような \(K\) と同符号の \(K_1, K_2\) を使って \(K_1 \min _ {w_1} w_1 f(X ; w_1) + K_2 \min _ {w_2} w_2 f(X ; w_2)\) としても同じである。 これにより変数の数を犠牲にして係数の最大値を落とせる。

後処理として最後にやると実装がきれいだが、その場合 \(K\) は関連する項の係数の \(\gcd\) として取り出す必要があることに注意する。

考察: コンテストに関するもの

採点方法

入力 \(X\) をすべて \(1\) と設定した場合と一様ランダムに設定した場合を試してその \(2\) 回の点数の平均。 \(e _ {SA} = 0\) は常に達成できるとしてよいので、制約を満たす出力であるとき点数は次の \(2\) 変数の積 \(\mathrm{PY}' \mathrm{PZ}'\) に比例する。これを最大化すればよい。

\[\begin{array}{lll} \mathrm{PY}' & = & \frac{1}{5 M + L + 1000} \\ \mathrm{PZ}' & = & \frac{1}{C + 1000} \\ \end{array}\]

ただし

  • \(M\) は新規変数の個数
  • \(L\) は項数 (定数項を含む)
  • \(C\) は係数の絶対値の最大値 (定数項は含まない)

嘘

入力 \(X\) がすべて \(1\) の場合は自明で、定数 \(c = f(1)\) として \(g = c\) を提出すれば理論値が得られる。 そうでなくても値だけ合わせにいけばよいのでほぼ考えなくてよい。 一様ランダムの場合も緩くて、高次の項 \(x_1 x_2 x_3 \dots x_d\) が \(1\) になる確率は \(\frac{1}{2^d}\) しかないのでそれらは無視して構わない。 テストがたったの \(100\) ケースしかないのでかなり冒険してよく、特に高次の項を無視できる問題Aはただの運ゲーである。

正の項と負の項は性質が違うので分けて考えるべきで、打ち切る次数も同じがよいとは限らない。 とりあえず \(15000\) ケースほどを試せば十分なはずで、まとめると次のようになる。

  • 次数 \(10\) 以上の正の項と次数 \(10\) 以上の負の項を潰したとき、 \(15000\) ケースで失敗は \(3\) ケースかつ点数の総和は \(0.8860 \times 10^{12}\) 点
  • 次数 \(8\) 以上の正の項と次数 \(8\) 以上の負の項を潰したとき、 \(15000\) ケースで失敗は \(17\) ケースかつ点数の総和は \(0.9931 \times 10^{12}\) 点
  • 次数 \(7\) 以上の正の項と次数 \(7\) 以上の負の項を潰したとき、 \(15000\) ケースで失敗は \(44\) ケースかつ点数の総和は \(1.0556 \times 10^{12}\) 点
  • 次数 \(7\) 以上の正の項と次数 \(6\) 以上の負の項を潰したとき、 \(15000\) ケースで失敗は \(45\) ケースかつ点数の総和は \(1.0964 \times 10^{12}\) 点
  • (次数 \(6\) 以上の正の項と次数 \(7\) 以上の負の項を潰したとき、 \(1500\) ケースで失敗は \(13\) ケースかつ点数の総和は \(1.10 \times 10^{11}\) 点)
  • (次数 \(6\) 以上の正の項と次数 \(6\) 以上の負の項を潰したとき、 \(1500\) ケースで失敗は \(13\) ケースかつ点数の総和は \(1.12 \times 10^{11}\) 点)

特に \(100\) ケースで考えたとき

  • 次数 \(8\) 以上の正の項と次数 \(8\) 以上の負の項を潰したとき、 \(100\) ケースでのどれかで失敗する確率は \(10.72\%\)
  • 次数 \(7\) 以上の正の項と次数 \(6\) 以上の負の項を潰したとき、 \(100\) ケースでのどれかで失敗する確率は \(25.95\%\)

URL