つーさのくーかん

スーパーテンパズル http://shindanmaker.com/198886

今回はこれを解いてみたくなったんだ。

さて、どうやって解くか……。

注意：プロコン系の話です。

まずは対象とする解の空間は全探索できるほど狭いのかどうかを考えてみますかー。
つまり、７つの数字、7種類のオペレータから構成できる式が何通りあるのか？

とりあえず、記号1種類で考えてみますか？
(a*a)*(a*a)*(a*a)*a とか ((a*(a*a)*a)*)a*a)*a とか。なんかいっぱいありそう。

ここで、オペレータは全て２つのオペランドをとるものなので、
解の候補となる式は葉が７つで節が６つの２分木っぽい構文木で表せるはずですね。
この条件を満たす計算木が何種類あるのかがわかれば式の形が何通りあるかわかりそう。

葉が７つで節が６つの計算木で表せるなら13文字の逆ポーランド記法で表せるはずですね。
aがオペランドでxがオペレータとすれば aaaaaaa****** や aa*a*a*a*a*a*a のような形。
こういった文字の並びが何通りあるかを考えればいいわけですよね。
おお、だいぶ数えやすくなりました。

ただ、 aa* はOKでも、 *aa や a*a はNGなので……。
最初のaは確定で、以降のi文字目時点で、未使用a個数<=未使用*個数 を満たせばいい？

列挙して数えてしまいましょう。電☆卓！(python)

>>> def f(a, b):
...   if a < 0 | b < 0:
...     return 0
...   if a == 0 & b == 0:
...     return 1
...   if a < b:
...     return f(a-1,b) + f(a, b-1)
...   else:
...     return f(a-1,b)
>>> print f(7,6)
132

あら意外と少ない。
上で書いたような括弧の式は132通りしか種類がないってことです？

後は各aに当てはめる数字が7種類の中から1回ずつなので 7!通り
*に当てはまる記号は7種類が何回でも使っていいので 7^6通り。

よって、式の候補は 132*7!*7^6 = 132 * 5040 * 117649 = 78269526720
約782億通り。

あら意外と多いですね。1秒間に1億通り試せれば約13分？
next_permutationを二重でぶん回すと、式の構成にもっと計算が必要なので、
ちょっとゆっくりディナーに行く時間が確保できてしまいそうです。

7^6っていうのが存外大きいですねー。

それにしても、aのb乗根とか、log_a(b)とか……
整数になる組み合わせは稀ですが、単純に整数にならなかったとしても、
実は他の四則演算、4を掛けるなどがくっつくと整数に戻る可能性があるので、
結局ちゃんと計算して保持しないといけないような気がします？

aのb乗もあっさり桁あふれ起こしてくれちゃいそうで頭痛の種ですねぇ。
13^13^13^13^13^13^13 は ceil(log(13)*13^6)=5376792桁の10進数なので
単純計算で2MB近いメモリを使うますか。
これを何億回計算とか、ディナーでは済みそうにありませんねぇ。

このあまり使えなさそうな3つの演算に関しては、
ほとんど使えないくせに、何かしら対策が必要そうです。
四則演算だけだったら、するめの300くらいだと思うんですけどねー。

ふむ、今日はここまでにしときましょう。

ちなみに、診断メーカーの出題で、材料に1を引いた場合は、
log_n(1)は0になることを利用して要らない数字を掛けて捨てることができます。
残った数字でがんばるのは全部使うよりは楽そうですね！