※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

数学の勉強で昔こんな問題に挑戦したことがあります。

堀江 伸一

3*3*10^10000段のブロックタワーを2*1*1のブロックで構成したとき何通りの組み立て方があるか。
答えは答えを10億7だったかそんな数で割った余りを答えよという問題。

10億段とか1000兆段とかそういうちいさな段数でなく10001桁段です。

とりあえず楽しいパズルと考え何も調べ物をせず自力で考えたコードを要約すると以下の通り。


上面に0個以上出っ張りの飛び出た、下面に0個以上穴ぼこのあいた2段で可能なものを全て作ります。
その2段から二つ選び(同じものを二つ選んでもよい)可能な4段全てを作ります。
4段でも同様に8段を作り、同じように8段を組み合わせて16段を作ります。
これを10^10000段の直前まで作りつづけます。
つくった2倍段のブロックタワーは上下の凸凹以外で区別する必要がないので、上下の凸凹を主キーに値として組み合わせ数を保持すれば計算は意外とシンプルです。

10^10000段を2進数になおしたときあるn桁目に1のビットが立ってたら、2^n段を作れた時にそれをどんどんアセンブリして積み重ねていけば答えが出ます
細部は覚えてませんが大体この方法で6時間半パソコンに計算させて正しい答えが出ました。
なぜ2段から計算を始めたかというと10^10000を2進数になおしたとき1段単独からのアッセンブリーがなかったからです。
考えることが容易な2段から作った覚えがあります。
当時書いたときは1段から計算を始めるとプログラムが複雑になると考えてたようです。

例えば10段を2進数で表すと1010段ですが、これは8段と2段を組みあわせれば10段となります。
組み合わせた後、上面と下面にでこぼこのないセットの組み合わせ数を出力すれば答えとなります。

アセンブルするときに上面の凸凹が512通りのサブセット、下面の凸凹が512通りのサブセット、結合部の上面の凹凸が決まれば結合部下面の形が決まるので512通りのサブセット。
一つ結合するときにBigO(512^3)、必要な段数は10^10000=2^37000くらいなのでこの結合を37000回する必要があります。
BigO(512^3*37000)の計算です。

当時コードを書いたときは試行錯誤の残る多少非効率で無駄も入ったコードも書いていた覚えもあります。
実際は上面と下面に制約があるのでもうすこし計算量が落ちてましたが、6時間半もパソコンを回したのを覚えています。

正しいコードだと、30秒で答えが出るそうなのでもっと高度な発想が必要な問題だったようです。
正しい答えが出るからって計算に6時間半もかかっては不正解となったものでした。

ちなみに私は創価学会の方から小学校の足し算と掛け算までしかできない人間だとという悪いうわさを流されていますが。
本物の堀江伸一はこういう問題を趣味で解いている人間だったりします。
「堀江伸一さんだったら小学校の算数くらいだったら出来ますよ」
と窓全開はきはきした声で電話しうちまで聞こえてきた○○さんち。
多分創価学会女性陣は知らないと思うけど。
男性学会員は私を嘲笑うことを一生懸命楽しんでますよね多分。



http://www14.atwiki.jp/c21coterie/pages/597.html
さてこの問題を解くために昔書いたコードを見ると。
この問題はプロジェクトオイラーというサイトに掲載されている問題No324の問題なのですが。
とにかく自分で考えついたものを試しては駄目を繰り返しそのあとようやく答えにたどり着けた試行錯誤の跡が残りまくりの酷いコード。
どうしてこんな、意味不明で要領の悪いコードをたくさん書いたのだろう?
自分でも不思議。

この手の競技プログラムの問題に挑戦するたびに思うのですが。
今回はきちんとした答えにたどり着いていませんが(答えが出るまで時間かかりすぎ)。
正しい答えにたどり着けた問題で、問題を見返すとこんな簡単な考えで解けるのかと驚く問題が多いです。
答えにたどり着くと答えにたどり着くのに苦労した自分が不思議になる。
数回しかありませんがコード実行速度1位を取れたりした時は特に不思議な気分になります。
何故皆こんなシンプルな発想に気づかないのだろう?
そう思うこともあります。
多分この問題を正しく解いた人から私の発想を見るとなぜこんな頭の悪い発想で解いてるのだろうと思われてるのだと思いますが。

コード実行速度一位もあれだよな。
書いたときにはこれ以上早いコードは理論上ないだろと思って記述してネットで晒してんだけど。
後日見ると、抜かれてるってことがあったからな。
結局、真の一位ではなく、暫定一位なんだよな俺の場合、、、。

今回は私の思いついた方法は2倍段をつくって、条件に合うものが出来たら上に上にと積み立てていくだけ。
シンプルな発想なので実装に苦労した自分がいまみると無性におかしい。
シンプルな発想なのだからシンプルなコードが答えになるのに妙な技巧に走ってコードサイズが膨らみ自滅してる。
コードは間違ってないがナンセンスマシーンみたいにいらない処理がたくさんくっついてる。

今書きなおすなら。

dp[2][612][512]でブロックタワーの2倍段の組み合わせを動的計画法で求めるか。
最初の1段を再帰で求めて作って、あとは4重ループ。
一番外は約37000回、2倍段を作るループ。
その中に上面、下面、結合部面でブロックを結合する3重ループ。
それと、結合後、作ったブロックタワーを答えのためにアセンブリするコードも同じ要領で書くと。
アセンブリするコードと2倍段を作っていくコードは処理はほぼ共通だから、関数化すれば。
計算量は落とす方法は未だによくわからないが、今ならずっとシンプルに書けるなこれ。
すこしは勉強が進んでるのかもしれない。