2010年8月に出題されたこんな問題。
今更になって何故か唐突に思い出したので解いてみた話。
「1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 2.0の10個と + - × ÷ ( )を使って大きい数を作れ」という問題。10万以上から「ちょっと賢い」ラインだそうだけど1万も厳しい
— sylph01 / G4きゅーぶ (@s01) August 17, 2010
投稿主であるsylph01さんによる記事は以下。
この記事に付いたコメントに拠ると
- 可能な最大値は $3388220$
- プログラムで探索すると8.5時間（Core i3-530 2.93GHz; 3skさん）とか7時間（Core i7-860 2.8GHz; らすかるさん）とか掛かる
らしいのですが、まあ「上手く工夫すれば探索範囲を削減できるんでないの？」「並列処理可能な計算が多いんでないの？」「もうちょい最近のマシンならマシンパワーでゴリ押せる部分もあるのでは？」などと思わんでもなかったのでやってみました。
過去の経緯
筆者がこの問題に初めて取り組んだのはたぶん2013年6月で、当時 C, C++, OCaml, Haskell で幾つかの手法を試してみて途中で放り出した形跡がありました。
今回は、当時書き散らしていたソースコード片の中で今の筆者の目で見て比較的筋が良さそうに見えた OCaml のコードを利用してソルバを作成することにしました。
用語・記号の定義
本記事で使う用語・記号を以下の通り定めます。
- リテラル
- 定数 $1.1, \dots, 2.0$ のこと。リテラル全体の集合を $\Lambda := \{ 1.1, \dots, 2.0 \}$ と書く。
- 式
- 1 つ以上のリテラルと四則演算のみにより構成される数式であって、同じリテラルが複数回出現しないもの。式とその値（有理数値）とは適宜同一視する。
- 正規な式
- 全ての部分式の値が正である式。本問では正規な式だけを考えれば十分。
- $\mathrm{Lit}(e)$
- 式 $e$ に含まれる全てのリテラルからなる集合。
- $\mathrm{All}(A)$
- $\mathrm{Lit}(e) = A \subseteq \Lambda$ なる正規な式 $e$ 全体からなる集合。
- $\mathrm{Max}(A)$
- $e \in \mathrm{All}(A)$ なる正規な式 $e$ のうち値が最大であるもの（のうちの1つ）。
- $\mathrm{Min}(A)$
- $e \in \mathrm{All}(A)$ なる正規な式 $e$ のうち値が最小であるもの（のうちの1つ）。
- $A \sqcup B$
- 集合 $A, B$ の非交和（交わりを持たない集合同士の合併）。
戦略
机上での絞り込み
まずは求めるべき最大値を与える式 $\mathrm{Max}(\Lambda)$ としてあり得る形を机上でできる範囲で絞り込みます。
少し真面目に考えると、$\mathrm{Max}(\Lambda)$ は以下の3通りのいずれかの形であるとしてよいことがわかります。
（具体的な証明は別文書 [PDF]を参照）
- $\mathrm{Max}(\Lambda) = \dfrac{a}{(Z_1 - W_1) \times \dots \times (Z_n - W_n)}$ （但し $a \in \Lambda$）
- $\mathrm{Max}(\Lambda) = \dfrac{b + c}{(Z_1 - W_1) \times \dots \times (Z_n - W_n)}$ （但し $b, c \in \Lambda$）
- $\mathrm{Max}(\Lambda) = \dfrac{a \times (b + c)}{(Z_1 - W_1) \times \dots \times (Z_n - W_n)}$ （但し $a, b, c \in \Lambda$）
メモ化DP
式とはリテラルから始めて帰納的に構成される二分木ですので、メモ化DPで小さな $A$ から順々に $\mathrm{All}(A)$ を求めていけば全ての式を列挙することができる筈です。 \[ \mathrm{All}(A) = \begin{cases} A &\text{if $|A| = 1$} \\ \displaystyle \bigsqcup_{{A = B \sqcup C}\atop{{B \ne \emptyset}\atop{C \ne \emptyset}}} \begin{cases} \{ e_1 + e_2 \mid e_1 \in \mathrm{All}(B), e_2 \in \mathrm{All}(C) \} \\ {} \sqcup \{ e_1 - e_2 \mid e_1 \in \mathrm{All}(B), e_2 \in \mathrm{All}(C), e_1 > e_2 \} \\ {} \sqcup \{ e_1 \times e_2 \mid e_1 \in \mathrm{All}(B), e_2 \in \mathrm{All}(C) \} \\ {} \sqcup \{ e_1 \div e_2 \mid e_1 \in \mathrm{All}(B), e_2 \in \mathrm{All}(C) \} \end{cases} &\text{if $|A| > 1$} \end{cases} \]
ところが考えるべき $\Lambda$ 上の式というのは（絞り込み方にも依るが）数百億～数兆個ありますから、やってみるまでもなくわかる話ですが、全部をメモ化しようと思うと普通の PC ではメモリが枯渇してしまいます。
筆者の環境では $|A| \le 6$ なる $A$ については全ての $\mathrm{All}(A)$ をメモ化できましたが、$|A| \ge 7$ となるとちょっと無理がありました。
そこで、メモ化の方針を以下の通りとし、メモ化しきれない式は必要となる度に全走査することにしました。
- $|A| \le 6$ なる $A$ については $\mathrm{All}(A), \mathrm{Max}(A), \mathrm{Min}(A)$ を全てメモ化する
- $|A| = 7$ なる $A$ については $\mathrm{Max}(A), \mathrm{Min}(A)$ に限ってメモ化する
メモ化を前提とした絞り込み
この方針でメモ化した値を上手く活かせるように前述の $\mathrm{Max}(\Lambda)$ の形を分類し直すと、以下の3通りのいずれかとなります。
（$|X - Y|$ は「$X - Y$ か $Y - X$ かのうち値が正の方」と解釈してください）
- $\mathrm{Max}(\Lambda) = \dfrac{\mathrm{Max}(A)}{\mathrm{Min}(B)}$ （但し $|A| = 3, |B| = 7$）
- $\mathrm{Max}(\Lambda) = \dfrac{\mathrm{Max}(A)}{\mathrm{Min}(B) \times \mathrm{Min}(C)}$ （但し $|A| \le 2, 2 \le |B| \le |C| \le 7$）
- $\mathrm{Max}(\Lambda) = \dfrac{\mathrm{Max}(A)}{|X - Y|}$ （但し $|A| \le 2, |B| \le |C| \le 8, X \in \mathrm{All}(B), Y \in \mathrm{All}(C)$）
このうち 1. や 2. のケースは、メモ化さえ済んでしまえばあとは $\Lambda = A \sqcup B$ 或いは $\Lambda = A \sqcup B \sqcup C$ と分割してそれぞれの $\mathrm{Max}$ や $\mathrm{Min}$ を拾えば良いだけなので一瞬です。
問題は 3. のケースですが、この場合も全ての $X \in \mathrm{All}(B), Y \in \mathrm{All}(C)$ の組合せを走査する必要はありません。
$|B| \le 4$ ですので、少なくとも $\mathrm{All}(B)$ はメモ化できている筈ですから、
値の大きさに関して整列した配列など、$\mathrm{argmin}$ を見つけやすいようなデータ構造で $\mathrm{All}$ を保持すると良いでしょう。
特に $\mathrm{All}(B)$ も $\mathrm{All}(C)$ も共にメモ化できている場合は、より小さい集合である $\mathrm{All}(B)$ を外側にして
メモ化の省略
上で $\mathrm{All}(A)$ を「$\mathrm{Lit}(e) = A \subseteq \Lambda$ なる正規な式 $e$ 全体からなる集合」と定義しましたが、実のところこれも愚直に全ての式をメモ化しておく必要はありません。
例えば $1.5 \div 1.2 - 1.1$ と $(1.2 - 1.1) \times 1.5$ のように、同じリテラルからなる同じ値の部分式は任意に交換可能ですから、どちらか一方だけ保持しておけば十分です。
これも走査すべき式の削減に大きく寄与します。
| $|A|$ | 走査した個数 | メモ化した個数 |
|---|---|---|
| 1 | 10 | 10 |
| 2 | 225 | 225 |
| 3 | 6,117 | 5,551 |
| 4 | 165,684 | 137,289 |
| 5 | 4,043,531 | 2,708,440 |
| 6 | 77,883,253 | 40,056,068 |
| 7 | 1,115,237,412 | - |
勿論 $2.0 - (1.9 - 1.8)$ と $2.0 - 1.9 + 1.8$ のように明らかに等価な式は走査自体を省略してしまうこともできます。
（式の構築時に「減算のオペランドとして減算を許容しない」のような制約を課すことで実現可能）
並列計算
上述の通り今回は OCaml を採用することにしたのですが、幸いなことにこの12年間で OCaml も進化しており、なんと OCaml 5 で導入された Domain というモジュールを使うと特に困難無く並列プログラムを書くことができます（昔は threads という名のニセモノしか無かった）。
本問では互いに独立な部分問題を多数解くことになるので、並列化の効果は絶大です。
結果
実行環境
- CPU Intel(R) Core(TM) i7-10700 CPU @ 2.90GHz （8コア16スレッド）
- メモリ容量 16216884 kB
- OS Ubuntu 24.04.3 LTS (Noble Numbat)
ソルバ
ソースコードは GitHub にて公開しています。
- 言語 OCaml 5.4.0
- コンパイラ ocamlopt 5.4.0
- 使用ライブラリ Zarith 1.14
- 有理数演算モジュール Q を使用
問題の性質上、浮動小数点数演算で探索した場合にどれだけ桁落ち誤差が発生するかを見積もるのは困難なため、ちゃんとやるなら有理数演算で解くべきです（一応、浮動小数点数演算でも同じ答えは求まりました）。
また、有理数演算の方が等値性の判定が確実なので、上述の「同じ値の部分式は省略する」という削減策がちゃんと効きます。
実行結果
- 所要時間
- 有理数演算でちゃんとやった場合: 約33分
- 浮動小数点数演算で済ませた場合: 約8分半
- 使用メモリ容量 約 11 GiB
- 得られた最大値 $2.0 \div (1.1 - 1.6 \div (1.3 + 1.8 \div ((1.2 + (1.4 + 1.5) \times 1.7) \times 1.9))) = 3388220$
走査した式（完成形）の個数
合計45,419,787,446個。先人達が何千億～何兆と言っているのと比べると、桁1つ～2つ減らせました。
- $\mathrm{Max}(\Lambda) = \dfrac{\mathrm{Max}(A)}{\mathrm{Min}(B)}$ 形: 120個
- $\mathrm{Max}(\Lambda) = \dfrac{\mathrm{Max}(A)}{\mathrm{Min}(B) \times \mathrm{Min}(C)}$ 形: 7,815個
- $\mathrm{Max}(\Lambda) = \dfrac{\mathrm{Max}(A)}{|X - Y|}$ 形: 45,419,779,511個
所感
やっぱりちゃんと机上で絞り込むのが大事。
