2019-04-08

Codeforces 1119H: Triple

Codeforces

https://codeforces.com/problemset/problem/1119/H

問題概要

$x, y, z$ が固定されている． $i = 1, \ldots, n$ に対して $a_i, b_i, c_i \in \{0, 1, \ldots, 2^k-1\}$ が与えられるので， $x T^{a_i} + y T^{b_i} + z T^{c_i}$ たちを $T$ の指数は XOR で畳み込む，というのを速くやる．

考察

Hadamard 変換すれば畳み込みが掛け算になる (常識) けど，そのままやると長さ $2^k$ の列を $n$ 個作らなければいけなくてダメ．

$x T^{a_i} + y T^{b_i} + z T^{c_i}$ を Hadamard 変換すると $v$ 項目は $(-1)^{\langle v, a_i \rangle} x + (-1)^{\langle v, b_i \rangle} y + (-1)^{\langle v, c_i \rangle} z$ になる ( $\langle , \rangle$ は $k$ ビットの整数を長さ $k$ のベクトルと見た内積) (定義)．ので，出てくる値は $\pm x \pm y \pm z$ しかない (これは定義に戻ることを忘れていても実験すればわかる)．ので， $v$ 項目の積は $(+ x + y + z)^{e_{000}} (- x + y - z)^{e_{100}} (+ x - y + z)^{e_{010}} \cdots$ みたいになって ( $e_{000}$ とかは $v$ に依存)， $x, y, z$ とか関係なくて $2^3$ 個の指数が上手く求まればうれしい．例えば $e_{000}$ は $\langle v, a_i \rangle, \langle v, b_i \rangle, \langle v, c_i \rangle$ が全部偶数になるような $i$ の個数とかそういう．手早く数えられそうでできない (「数える」という考えから抜けられなくてコンテスト中はここで止まった)．

「 $x, y, z$ とか関係なくて」とか言ったんだから特殊な値を代入して何かしてみるべき (極めて一般的な手法)．例えば $(x, y, z) = (1, 0, 0)$ として (これは自然な「特殊な値」)， $\prod_i (-1)^{\langle v, a_i \rangle} = (-1)^{e_{100}} (-1)^{e_{110}} (-1)^{e_{101}} (-1)^{e_{111}}$ だけど，これすら各 $v$ について手早くのは難しそうなうえに得られる情報量が少ない (普通の感想)．得られる情報量を多くしようとして指数の底を $0$ とか $\pm 1$ とかじゃないようにしても綺麗になる気配はない (たぶん普通の美的感覚)．ということで，代わりに $\sum_i (-1)^{\langle v, a_i \rangle} = + e_{000} - e_{100} + e_{010} - e_{110} + e_{001} - e_{101} + e_{011} - e_{111}$ を考えよう (これは，お気持ちはわからなくはないけど，かなり賢いと思う)．左辺は Hadamard 変換の線形性を使えるうれしい形をしていて， $\sum_i T^{a_i}$ を一度変換すれば各 $v$ について求まる．

同様に $\sum_i (-1)^{\langle v, b_i \rangle} = + e_{000} + e_{100} - e_{010} - e_{110} + e_{001} + e_{101} - e_{011} - e_{111}$ と $\sum_i (-1)^{\langle v, c_i \rangle} = + e_{000} + e_{100} + e_{010} + e_{110} - e_{001} - e_{101} - e_{011} - e_{111}$ が求まることがわかった．あとどんな関係があれば $e_{000}$ とかを特定できるか？というと，長さ $2^3$ の Hadamard 変換っぽい見た目をしているので (Hadamard 変換の問題を解いているのだから Hadamard 変換っぽい見た目には気づく)， $+ e_{000} - e_{100} - e_{010} + e_{110} + e_{001} - e_{101} - e_{011} + e_{111}$ とかそういうやつがほしい．それは $\sum_i (-1)^{\langle v, a_i \rangle} (-1)^{\langle v, b_i \rangle}$ とかで，そんなのが求まるかというと，よく見ると $\sum_i (-1)^{\langle v, a_i \oplus b_i \rangle}$ なのでうれしい (冷静さが必要)．これでできたのでまとめると，

解法

$\sum_i T^{0}, \sum_i T^{a_i}, \sum_i T^{b_i}, \sum_i T^{a_i \oplus b_i}, \sum_i T^{c_i}, \sum_i T^{a_i \oplus c_i}, \sum_i T^{b_i \oplus c_i}, \sum_i T^{a_i \oplus b_i \oplus c_i}$ のそれぞれを Hadamard 変換する．
各 $v$ に対して， $v$ 項目を集めて長さ $2^3$ の列にして Hadamard 逆変換すると， $(+ x + y + z)^{e_{000}} (- x + y - z)^{e_{100}} (+ x - y + z)^{e_{010}} \cdots$ の各指数が得られるので，計算する．
というのを並べて，Hadamard 逆変換すると答え．

$3$ 項しかないというのの $3$ は小さいことしか本質ではなくて， $m$ 項だったら $O(2^m m n + 2^m 2^k k + 2^k 2^m m)$ 時間とかでできますね．

思考の整理のために書いてみたのですが，賢いところが一箇所な割にはすごいことができていて，不思議な感じが残りました．

2018-12-28

Xmas Contest 2018

Xmas Contest 2018 にご参加いただいた皆様，どうもありがとうございました！

2015, 2016, 2017 年は元気にしていなくて開催できなかったのですが，その間引き継いでくれていた japlj さんと snuke さんと共に今年は運営しました．とっつきやすい良問を作ってもらったり (A, F, G)，雑に提案したのをちゃんと解いてもらったり，クリスマスコンテストっぽくない問題をちゃんと却下してくれたり，いろいろやってもらえて助かりました．

わたしが原案を出した問題の解説をこのブログに載せておきました．変なとこがあったら教えてください．数式多めなので環境によっては見づらいかもしれませんごめんなさい．

2018-12-28

Xmas Contest 2018 J: Japanese Exponentation 解説

Xmas Contest 2018

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

問題概要

四の三の二乗乗 みたいなのを $\operatorname{mod} (10^9 + 9)$ で計算せよ．

解法

UTF-8 の文字列を処理する方法は，皆さんお使いのプログラミング言語ごとに調べてください．

冪乗を $\operatorname{mod} m$ で計算する方法を考えます．「 $a_1 \equiv a_2 \pmod{m}$ のとき $a_1^b \equiv a_2^b \pmod{m}$ 」は正しいですが，「 $b_1 \equiv b_2 \pmod{m}$ のとき $a^{b_1} \equiv a^{b_2} \pmod{m}$ 」は正しくないので，指数は勝手に $\operatorname{mod} m$ をとってはいけません．

とはいえ， $\operatorname{mod} m$ での $a^0, a^1, a^2, \ldots$ は必ずどこかから周期的になります．最初から周期に入っているとは限りません．例えば $m = 12,\, a = 2$ のときは $1, 2, 4, 8, 4, 8, \ldots$ となり， $a^2$ から長さ $2$ の周期に入ります．どこからどんな長さの周期に入るかについては，以下の事実がよく知られており (補足参照)，この問題ではこれで十分です：

$b \ge \log_2 m$ なら， $a^b, a^{b+1}, \ldots$ は既に周期に入っている．
周期の長さは $\varphi(m)$ の約数である．ただし $\varphi$ は Euler の φ 関数．

というわけで，指数はおおよそは $\operatorname{mod} \varphi(m)$ でもっておけばいいですが，小さい値，雑に $32$ 未満くらいは特別に扱う必要があります．実装上は，例えば次のいずれかのような方針がわかりやすいと思います：

$\operatorname{mod} m$ をとる代わりに， $32$ 以上の整数は $32, \ldots, 32 + m - 1$ に収めるようにする ( $x \, (\ge 32)$ を $32 + ((x - 32) \bmod m)$ にする)．
整数 $x$ の計算結果として， $(x \bmod m, \min\{x, 32\}$ ) の組をもつ．

以上をふまえると，構文解析パート (再帰下降) を合わせて解答は次のようになります．

Result expr(m):  // Result 型は上記のように特殊な mod のとり方をした整数
  Result a := number(m)  // 整数を読む
  while 次の文字が "の":
    "の" を読む
    Result b := expr(φ(m))
    a := a^b  // 繰り返し二乗法などで計算
    "乗" を読む
  return a

なお， $10^9+9, \varphi(10^9+9), \varphi(\varphi(10^9+9)), \ldots$ は $25$ 回で $1$ になるので，同じ $\varphi$ の計算を複数回しないようにすれば実行時間は大丈夫です．

補足

$\operatorname{mod} m$ での $a^0, a^1, a^2, \ldots$ の様子について，もうちょっとちゃんとした話をします．

中国剰余定理より， $m$ としては素冪 $p^e$ だけ考えればよいです．素冪ごとに考えた後で，周期に入る場所は $\max$ をとればいいし，周期の長さ (の倍数) は最小公倍数をとればいいです．

$a = p^k a_0$ ( $k$ は非負整数， $a_0$ は $p$ で割れない) と書くと， $k \ge 1$ のとき $p^k$ の部分は累乗していくと途中からずっと $0$ になってしまい，これが周期の前の部分を作っている要因です．高々 $e$ 乗で $0$ になるので，周期に入るまでの長さは $e$ 以下です．一方 $a_0$ の部分だけ見ると最初から周期に入っていて，その周期は

$p = 2$ かつ $e \ge 3$ のとき $2^{e-2}$
その他のとき $p^{e-1} (p - 1)$

の約数です．さらに，実際にこれらの周期をとる $a_0$ が存在します (原始根の存在定理など)．

ここまで考察すると，この問題で必要な $\operatorname{mod}$ は $1000000009, 1000000008, 977076, 4428, 360, 12, 2, 1$ だけで済むことがわかります．

この問題は，本当に問題文のストーリー通りの流れで作りました．「 $a$ の $b$ 乗」の構文は，

の を開き括弧 (，乗 を閉じ括弧 ) だと思うと関数適用の式
の を区切り文字，乗 を演算子だと思うと逆ポーランド記法

になっていて面白いです．

マルチバイト文字は，こういうコンテストだからこその出題という感じですね．いろいろ調べていたら 六 にだけ互換文字があるとかいう知識が増えてしまいました．

数学パートは，「普段なんとなくで $\operatorname{mod}$ をとっていませんか？」というメッセージ (?) です．

2018-12-28

Xmas Contest 2018 I: Interesting Equation 解説

Xmas Contest 2018

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

問題概要

実数 $X$ が与えられるので， $\lvert a X^3 + b X^2 + c X + d \rvert$ がだいたい $0$ になるような整数 $a, b, c, d$ を求めよ．

解法 ?

$\lvert a \rvert, \lvert b \rvert, \lvert c \rvert \le 10^4$ なる解の存在が保証されているので，その範囲の $a, b, c$ をすべて調べられれば答えが見つかります．

もちろんそれでは遅すぎるので，半分全列挙のようなことを行いたいです． $a X^3 + b X^2$ の小数部分たち， $c X$ の小数部分たちをそれぞれ列挙すると，ソートして尺取法などを行うことによって答えを探せます．これでも片方は $4 \times 10^8$ 通りほど列挙しなければならないので厳しいですが，何回か提出して $a, b$ の範囲を適当に制限するなどの方法で正解することができるかもしれません (実際，コンテスト中にこのような解法が何件か正解していました)．

解法 1

より均等に分けた半分全列挙を行うことができます．例えば $b = 100 b_1 + b_2$ ( $-100 \le b_1 \le 100$ ， $0 \le b_2 \lt 100$ ) と表すことができ， $a X^3 + 100 b_1 X^2$ の小数部分たち， $b_2 X^2 + c X$ の小数部分たちを列挙します．するとどちらも $10^6$ 程度のサイズとなり，十分高速となります．

チーム aadeeggimrsstuw がこの解法で正解していました．

解法 2

$M$ を十分大きい値として， $\mathbb{R}^4$ の $4$ 本のベクトル

$\begin{align} u_1 &= (1, 0, 0, \lfloor M X^3 \rceil), \\ u_2 &= (0, 1, 0, \lfloor M X^2 \rceil), \\ u_3 &= (0, 0, 1, \lfloor M X \rceil), \\ u_4 &= (0, 0, 0, \lfloor M \rceil) \end{align}$

を考えます ( $\lfloor \alpha \rceil$ は $\alpha$ に最も近い整数とします)．これらの整数係数線型結合であって長さが十分短いものを見つけられれば，それが答えになります：整数 $a, b, c, d$ に対し $a u_1 + b u_2 + c u_3 + d u_4$ の長さが短いとき， $a, b, c$ は小さく， $a X^3 + b X^2 + c X + d$ は $\frac{小さい数}{M}$ くらいなのでだいたい $0$ ，という気持ちです．

「整数係数線型結合で長さが十分小さいもの」を見つける方法として，LLL Algorithm が知られています．詳しい説明は web にいろいろな資料があるので，ざっくりだけ紹介します．

集合 $\mathbb{Z} u_1 + \mathbb{Z} u_2 + \mathbb{Z} u_3 + \mathbb{Z} u_4$ (格子と呼ばれます) を変えないように $u_1, u_2, u_3, u_4$ を変形していきます．変形の操作は次の $2$ 種類からなります：

いい感じの条件を満たすように $u_i$ を並べ替える．
$u_1, u_2, u_3, u_4$ に Gram-Schmidt の直交化を行ったものを $v_1, v_2, v_3, v_4$ とする． $i > j$ に対し， $u_i$ を $u_i - \left\lfloor \frac{\langle u_i, v_j \rangle}{\langle v_j, v_j \rangle} \right\rceil u_j$ で置き換える．

これをいい感じの順番で行うのが LLL Algorithm で，一般の $n$ 次元でも多項式時間で最適解の $2^{\frac{n-1}{2}}$ 倍の長さのベクトルが得られるそうです．すごいですね．一応なぜ直交化したいかの気持ちを説明すると， $\det(u_1, u_2, u_3, u_4)$ は生成する格子にしかよらず (格子の体積)，これは基底が直交していれば長さの積，ななめっていれば長さの積より小さくなっていくので，体積一定では直交に近いほうが長さが短い，という感じです．

この問題では，がんばって評価をすると， $M = 10^{16}$ ととれば制約下で正解が保証できることが示せます (ごちゃごちゃしてしんどいだけなので省略します)．演算は double 等でも大丈夫だと思いますが，多倍長有理数で時間に余裕を持ちつつ正確に行うこともできます．

omeometo さんの解法は，LLL Algorithm の代わりに， $u_i$ を $u_i - \left\lfloor \frac{\langle u_i, u_j \rangle}{\langle u_j, u_j \rangle} \right\rceil u_j$ で置き換えるというのをランダムな $i, j$ を選んでたくさんやっていました．ベクトルが短くなっていく感じはほぼ同じなので，十分な回数回していれば落ちなさそうです．

コンテスト開始直後，全 $0$ ではないという条件が抜けていました．そういうつもりじゃなかったんです，でもクリスマスコンテストならそういうのありえますよね……．ごめんなさい．

想定解は解法 $2$ で，無理問だけど強引にも通せるかも？くらいに思いながら出題しました．予想より正解者数が多かったです．特に解法 $1$ は全く気付いていなかったのでなるほどという感じでした．

問題文冒頭はさすがにやりすぎですが， $2$ 次式の根で $\pi$ を近似すると $\frac{71 + \sqrt{2156141}}{490} = 3.1415926536\ldots$ なんてのが得られたり，LLL Algorithm でいろいろ遊んでみると楽しかったです．

2018-12-28

Xmas Contest 2018 H: Hello, Xmas Contest 2018 解説

Xmas Contest 2018

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

問題概要

文字列 $S, T$ が与えられる．グリッドの一部に A-Z または * を書いて，

各行の最初の非空白文字を順に繋げて * を除いた文字列が $S$
各列の最初の非空白文字を順に繋げて * を除いた文字列が $T$

となるようにする．最低何文字書く必要があるか？ (入出力例の図を見るのがわかりやすいです)

解法

ある文字 $c$ が $S$ に $a$ 回， $T$ に $b$ 回現れたとすると，文字 $c$ は少なくとも $\max\{ a, b \}$ 個書かなければいけません．これを A-Z について足すことで答えの下界が得られます．

この下界はだいたい達成できそうな気がします：

 |AAACCB
-+------
A|A.....
A|.AA...
B|.....B
C|...CC.
B|......

具体的には， $S$ と $T$ の両方に現れる文字は問題なく配置できます．片方にしか現れない文字がある場合は，

 |UNAGI
-+-----
U|UN...
S|S....
A|..A..
G|...G.
I|....I

 |BAD
-+---
A|.AD
B|B..
C|C..

のように $1$ 行目の文字や $1$ 列目の文字で隠してしまえばよいです．隠せないのは，

 |AC
-+--
W|..
A|AC

のように $1$ 行目の文字が $T$ に現れない場合，あるいは $1$ 列目の文字が $S$ に現れない場合，のみです．そのような場合は * を $1$ 個以上書く必要があり，逆に * を $1$ 個左上に書いてしまえば隠したい文字を隠せます (看板を作ることが不可能なケースはありません)．

まとめると，

A-Z のそれぞれについて， $S$ に現れる個数と $T$ に現れる個数の $\max$ をとって足し，
$S$ の先頭が $T$ に含まれない，あるいは， $T$ の先頭が $S$ に含まれない，という場合だけ $1$ を足す

と答えになります．

最初は，色のついた積み木を積んだときの見取り図が $2$ 方向から与えられる，という設定で解こうとしていて，しかし高さ $2$ 以上のときわからなかったので高さ $1$ にしたら，無意識に昨年の問題と同じような設定になっていました．

制約は，解法を絞らせないために敢えてゆるくしました．

2018-12-28

Xmas Contest 2018 E: Exclusive☆OR 解説

Xmas Contest 2018

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$ を全探索していろいろ気づいた，という流れでありました．

2018-12-28

Xmas Contest 2018 D: Devilish Dice 解説

Xmas Contest 2018

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

問題概要

$N$ 個の $K$ 面さいころの目を上手く決めて，「どのさいころについても，他のあるさいころを選ぶと確率 $p$ 以上でそれより大きい目が出せる」となる $p$ を最大化せよ．

考察

くろうさ「先にさいころ選んでいいよ」

しろうさ「やさしい」

くろうさがやさしいわけはなく (?)， $N \ge 3$ かつ $K \ge 3$ ではこれはくろうさ有利なゲームです．例えば， $X_1 = (1, 7, 8),\, X_2 = (2, 3, 9),\, X_3 = (4, 5, 6)$ という $3$ 個のさいころを考えると， $\Pr[ X_1 \lt X_2 ] = \frac{5}{9},\, \Pr[ X_2 \lt X_3 ] = \frac{6}{9},\, \Pr[ X_3 \lt X_1 ] = \frac{6}{9}$ となり，三竦みの関係が生じます．他にも大量の例が https://en.wikipedia.org/wiki/Nontransitive_dice に載っています．

とても手に負えなさそうですが，問題を単純化できる考察がいくつかあります．まず，別のさいころに同じ値を書く意味はありません．同じ値があるとき片方を少し増やしてもくろうさは何も損しないからです (くろうさの勝率 $\min\{ \max\{\ldots\}, \ldots, \max\{\ldots\} \}$ の中身が増えるだけなので)．

また，「 $n$ 竦み」のような関係のみ考えればよいです．あるさいころに対して，それに強いさいころ，さらにそれに強いさいころ，……というようにとっていくとサイクルができるので， $n \le N$ に対する，「 $\Pr[ X_1 \lt X_2 ] \ge p,\, \ldots, \Pr[ X_{n-1} \lt X_n ] \ge p,\, \Pr[ X_n \lt X_1 ] \ge p$ となる最大の $p$ 」で答えが上から抑えられます．逆にこういうサイクルをひとつ作ってしまえばあとは弱いさいころを好きなだけ足せばよいです．

解法 1

ここまでを念頭にマシンパワーで DP をします． $K$ を固定します．

さいころ $X_1, X_2, \ldots$ の順で目を決めていくことにすると， $X_{i+1}$ を決めるときには $X_1$ と $X_i$ 以外の情報は要りません．ということで， $X_1$ と $X_i$ の目の大小関係を状態 ( $\binom{2K}{K}$ 通り) として， $\min\{ \Pr[ X_1 \lt X_2 ], \dots, \Pr[ X_{i-1} \lt X_i ] \}$ を最大化する DP をします．

DP の遷移をするには， $X_1$ と $X_i$ の大小関係それぞれに対する， $X_1$ と $X_i$ と $X_{i+1}$ の大小関係 ( $\binom{3K}{K}$ 通り) が一見要りそうですが， $X_1$ と $X_{i+1}$ の大小関係を決めてしまえば十分で，なぜならその制約の下では $X_{i+1}$ を $X_i$ に対してできるだけ強くしてしまってよいためです．

DP テーブルをどの $n$ まで作るかですが，やってみるとそのうち変わらなくなるので打ち切れます ( $K \le 10$ なら実は $n = 6$ までしか要りません)．あるいは後述のように $K$ に対する勝率の上限を求めておいてそれを達成したら打ち切る，というのもできます．

こんな感じで， $\binom{2K}{K}^2$ に多項式がかかったような計算量で解けるので，がんばって回して答えを埋め込みましょう．細かい定数倍高速化としては，例えば「 $X_1$ が目の最大値を持つことにしてよい」を採用すると $4$ 倍速くなって嬉しいです．わたしのコードは実行時間 $6$ 分くらいでした．

japlj さんと snuke さんは，ちょっと別のアプローチのマシンパワー探索解法をしていました．答えを決め打って必要な $N$ を求めにいく方針で，枝刈りが上手く効くようです．

解法 2

いろいろ実験をすると，「 $i$ 番目のさいころには $i$ と $i+N$ しか書かない」というパターンで結構いい感じの勝率が得られていそうなことに気づけるかもしれません (後述のように，これはただの偶然でも突拍子もない発想でもないです)．実際に $K \le 10$ ではこれですべて正解できるようです．

コンテスト中の hogloid さん，終了直後の omeometo さんの解法がこのパターンを見つけた方針でした．コンテスト前には，snuke さん作のゲームを手で遊んだ結果から似たようなパターンを試していたのですが，変な greedy をしていて $(N, K) = (4, 7), (5, 8)$ で不正解になっていたので，全探索系以外は厳しいかも？と思っていたのでした．

このパターンを仮定するなら，いろいろな解法が考えられます．例えば，「 $1$ 番目のさいころの $1$ の個数」と「 $i$ 番目のさいころの $i$ の個数」を状態として持つ DP ( $O(K^3 N)$ 時間) が楽だと思います．

さて，この仮定が正しいかというと，実は反例があるようです． $(N, K) = (3, 27)$ で，

144444444444444444444444444
222222222225555555555555555
033333333333333336666666666

というさいころを考えると，くろうさの勝率は $\frac{443}{27^2}$ ですが， $2$ 値さいころだけではこれは実現できません．ただ，この反例のように，「 $1 \le i \le N - 1$ に対しては $i$ 番目のさいころには $i$ と $i+N$ しか書かない， $N$ 番目のさいころには $0$ と $N$ と $2N$ しか書かない」というパターンなら正しいのではないかと予想しています．証明を募集しています！！

参考 1 (fixed K)

$K$ を固定したときの勝率の最大値は $1 - \displaystyle\frac{\left\lfloor \frac{K+1}{2} \right\rfloor \left\lfloor \frac{K+2}{2} \right\rfloor}{K^2}$ です．

これは，「中央値が最小」みたいなさいころを考えることで上から抑えられます．正確には， $n$ 竦みの中で自身の $t$ 番目の値が最小のさいころを考えると，それは他のさいころに高々 $1 - \frac{t (K+1-t)}{K^2}$ でしか勝てないので， $t = \left\lfloor \frac{K+1}{2} \right\rfloor$ ととることで示せます．この評価の仕方は， $2$ 値さいころだけを考えてもかなり上手くいくことを示唆しているかもしれません．

最大値をとる具体的な構成もできて，例えば $K = N$ として，「 $i$ 番目のさいころには $i$ が $i$ 個で残りは $i + N$ 」というようにすればよいです ( $N$ はもっと小さくとれます)．

$K \to \infty$ とするとこの値は $\frac{3}{4}$ になります．さいころに限らない一般の確率分布を考えても，勝率は $\frac{3}{4}$ が上限ということですね．

参考 2 (fixed N)

$N$ を固定したときの勝率の上限は $1 - \displaystyle\frac{1}{4 \cos^2\left( \frac{\pi}{N+2} \right)}$ です (!?)． $N = 1, 2, 3, 4$ ではそれぞれ $0, \frac{1}{2}, \frac{-1+\sqrt{5}}{2}, \frac{2}{3}$ となります．

詳しくは https://mathoverflow.net/a/119885 をご覧ください．

わたしは証明をちゃんと把握できていないのですが， $2$ 値の確率分布だけを考えればよいことを示すという方針のようです． $K$ が固定されているときに同じ議論は適用できないのですが， $2$ 値さいころだけを考える有力な根拠となります．解法 $2$ の最後で述べた予想も， $N$ を固定したときの最適解を近似したものがベストだろう，という考えに基づいています．

三竦みが作れるってだけでも面白いのにいろいろ楽しい数学が奥に潜んでいる，という感じの話題を，全部有限にして探索力 and/or 数学センスを問う問題にしてみました．不思議な問題ですね．

hos.lyric's blog

Codeforces 1119H: Triple

問題概要

考察

解法

コメント

Xmas Contest 2018

Xmas Contest 2018 J: Japanese Exponentation 解説

問題概要

解法

補足

コメント

Xmas Contest 2018 I: Interesting Equation 解説

問題概要

解法 ?

解法 1

解法 2

コメント

Xmas Contest 2018 H: Hello, Xmas Contest 2018 解説

問題概要

解法

コメント

Xmas Contest 2018 E: Exclusive☆OR 解説

問題概要

N = 1 のとき

N = 2 のとき

N = 3 のとき

N - 1 回解法

log N 回解法

行数制限

下からの評価

コメント

Xmas Contest 2018 D: Devilish Dice 解説

問題概要

考察

解法 1

解法 2

参考 1 (fixed K)

参考 2 (fixed N)

コメント