前回の記事はこちら。問題くらいしか参考になりません。というわけで昨日放置して寝てしまった問題解説とその後。
結局自分は10万ちょっと超えたところで挫折してしまいましたが、その後も恐ろしく話が進んでいたので続きを書きます。例によってネタバレがあるので続きを読む記法にて。
その後の展開
複数人によって出された1092000が最適解かと思われたのですがその後。
- [twitter:@xhl]さん：1701700 (20:47)
- [twitter:@xhl]さん：1992264 (21:13)
- [twitter:@i110]さん：2242912 (3:58)
- [twitter:@xhl]さん：3063060 (4:21)
なんと200万はおろか300万の領域に入ってしまいました。
予想
ここで「1092000は何かの前提を置いた上での最適解」の１つで、出題者が最上位ボーダーとして設定しているからには「手で出そうと思えば迫れる」ような前提の置き方なのではないか？と予想が立ちます。
解答方針
まず、「これって−と÷って使うの？」と思ったら「一般人」レベル。全部足して15.5、全部掛けて67、足し算かけ算のみの最大値が225。…って聞いてたけど、
(1.1 + 1.9) * (1.2 + 1.8) * (1.3 + 1.7) * (1.4 + 1.6) * 1.5 * 2.0 = 243
なのでもっとでかい数できました。243から一般人でいいと思います。
そこから先。
2.0 / (1.2 - 1.1) = 20
ということに気付ければ、あとは「いかに小さい数を作るか」というゲームになります。とりあえずでっかい数を小さい数で割ろう、という発想から
(2.0 + 1.9) / (1.8 - 1.7) / (1.6 - 1.5) / (1.4 - 1.3) / (1.2 - 1.1) = 39000
という数字が得られます。39000は最も多く@で飛んできた解答の1つでした。このあたりにもう１つライン引いていい気がします。
1.2 * 1.1 - 1.3 = 0.02
というのを使えば、
2.0 / (1.9 - 1.8) / (1.7 - 1.6) / (1.5 - 1.4) / (1.2 * 1.1 - 1.3)
で100000になります。ここが「ちょっと賢い」ライン。いやけっこう厳しいと思います…。
あとは試行錯誤してうまいこと0.1以下の数字、つまり掛けたら10以上になる数字を作る、ということになります。
ちなみに
(1.3 / 2.0) - (1.1 / 1.7) = 0.00294117647
が(a/b - c/d)型では最小。この形を使うと10万からちょっとだけがんばれますが厳しいです。
それでは100万以降について。ネタバレを気にしない場合それぞれの式の形をリンクをクリックすることで見てください。1092000とそれ以上の解答について違うところは、1092000は＋を１個も使用していないところ。これには手計算でたどり着いた人もいるようなので（そしておそらく問題制作者も手計算でたどり着いている）、手計算でやる場合には引き算・割り算のみを仮定して解けばこの数字にたどり着きます。他のパターンについては足し算などを含むため単純には行かないため発見されにくかった、ということでしょう。でもコード例を見る限り＋×を使用しないことを仮定しているわけではないけれど…？式の構造に関する暗黙の仮定があるのだろうか、括弧の使い方に関する暗黙の仮定があるのだろうか？
そうすると、果たして理論値はいくつなのか？という疑問が残ります。また、理論値であることの証明は可能なのか？という疑問も。括弧があるため、全数探索の探索対象は爆発的にふくれあがります。理論値であることを全数探索せずに証明することは可能なのか？組み合わせを試していくしかない以上部分的な全数探索を繰り返していくしかないような気もするが…
追記
> 括弧があるため、全数探索の探索対象は爆発的にふくれあがります。
具体的に何通りあるかは計算できますよ。
全て二項演算なので算術式の構文木を考えると、葉の数が10で（葉でない）枝の数が9の単純な全二分木になるので、それが全部で4862通り（9番目のカタラン数）。
葉は1.1〜2.0の10個の数の順列なので、10!=3628800通り。
（葉でない）枝は+-×÷のいずれかが独立して入るので4^9=262144通り。
全て掛け合わせて、4625065731686400通り。
（ただし+と×は可換ですがそれを考慮に入れていません、それを同一視すればもう少し減ります）
…でもこれをすべて調べようとしたら、1秒間に1000件確認できても15万年くらいかかる(^-^;
（[twitter:@antimon2]さんによるコメント）
二分木のパターン数を数えればいいのか！といってもその方法を知らなかったので調べてみた。ちゃんと対応する命名された数があるんですね。
(カタラン数 - Wikipediaより)
