解法概要

以下のようなもの:

  1. 高次の項を無視する
    • 具体的には、高次の項の係数の総和を として などの単一の項で置き換える
    • 調整した結果として次数 を無視
    • 嘘要素はここだけで、以降は厳密に一致する関数を得るような処理
  2. 次以下の項はそのまま使う
  3. 次以上の負の項は に還元
  4. 次以上の正の項は に還元
  5. 追加変数を分割することで係数の最大値を低減

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

まとめ

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


問題概要

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

ただし PBF とは整数係数の多項式 であって引数に真偽値しか考えないもの のこと。 QPBF とはその項を高々 次に制限したもの。

考察: QPBF に関するもの

前提: forall は簡単に作れる

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

冪等性

なので指数は考えなくてよい

否定

最小値

負の単項式

  • 新規変数:
  • 新規項数:
  • 最大係数:

結果は の順序に依存しない。

置換

と見做せる変数 を導入したい。 正整数 を適切に選んで式 を考えると、以下のようにして が設定される。

  • のときは なので
  • かつ やその逆のときは なので
  • のときは なので

ただし を他の場所で利用するとその使い方によっては であっても の場合の方が小さくなる可能性がある。 これは十分大きな整数 を用いて とすれば解決できる。

正の単項式: 単純な還元

  • 新規変数:
    • のときそれぞれ
  • 新規項数: (ただし定数項と新規変数を含まない 項を除く)
    • のときそれぞれ
  • 最大係数:
    • のときそれぞれ

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

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

正の単項式: higher-order clique reduction

  • 新規変数:
    • のときそれぞれ
  • 新規項数:
    • のときそれぞれ
  • 最大係数: のとき かつ のとき
    • のときそれぞれ

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

とおく。このとき

一般に が奇数のとき、

が偶数のとき、

になる。

単純な還元と違う点としては、変数の並びに依存せず のような新規変数を含まない項が 種類すべて使われること。

splitting of common parts

これは項を潰すのでなく変数を潰すもの。 係数がすべて正の式 と常に を満たす に対し とすると正の単項式の次数が落ちる。 正の単項式の単純な還元のちょうど 段階だけを複数の項に渡ってまとめて行なうようなイメージである。

例えば があったとする。 ただし係数はすべて正 とする。 なら かつ なら だが、そうなるように新規変数を導入すればよい。 であるような大きい整数 を置く。 このとき とする。 常に なので のとき となって 。 仮定から なので のとき となって 。 具体的には

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

係数の削減

という式があるときこれを であるような と同符号の を使って としても同じである。 これにより変数の数を犠牲にして係数の最大値を落とせる。

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

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

採点方法

入力 をすべて と設定した場合と一様ランダムに設定した場合を試してその 回の点数の平均。 は常に達成できるとしてよいので、制約を満たす出力であるとき点数は次の 変数の積 に比例する。これを最大化すればよい。

ただし

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

入力 がすべて の場合は自明で、定数 として を提出すれば理論値が得られる。 そうでなくても値だけ合わせにいけばよいのでほぼ考えなくてよい。 一様ランダムの場合も緩くて、高次の項 になる確率は しかないのでそれらは無視して構わない。 テストがたったの ケースしかないのでかなり冒険してよく、特に高次の項を無視できる問題Aはただの運ゲーである。

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

  • 次数 以上の正の項と次数 以上の負の項を潰したとき、 ケースで失敗は ケースかつ点数の総和は
  • 次数 以上の正の項と次数 以上の負の項を潰したとき、 ケースで失敗は ケースかつ点数の総和は
  • 次数 以上の正の項と次数 以上の負の項を潰したとき、 ケースで失敗は ケースかつ点数の総和は
  • 次数 以上の正の項と次数 以上の負の項を潰したとき、 ケースで失敗は ケースかつ点数の総和は
  • (次数 以上の正の項と次数 以上の負の項を潰したとき、 ケースで失敗は ケースかつ点数の総和は 点)
  • (次数 以上の正の項と次数 以上の負の項を潰したとき、 ケースで失敗は ケースかつ点数の総和は 点)

特に ケースで考えたとき

  • 次数 以上の正の項と次数 以上の負の項を潰したとき、 ケースでのどれかで失敗する確率は
  • 次数 以上の正の項と次数 以上の負の項を潰したとき、 ケースでのどれかで失敗する確率は

URL