「どうしても解けなかった数学の練習問題」の編集履歴（バックアップ）一覧に戻る
数学の勉強で昔こんな問題に挑戦したことがあります。
堀江 伸一
3*3*10＾10000段のブロックタワーを2*1*1のブロックで構成したとき何通りの組み立て方があるか。
答えは答えを１０億7だったかそんな数で割った余りを答えよという問題。
１０億段とか1000兆段とかそういうちいさな段数でなく10001桁段です。
とりあえず楽しいパズルと考え何も調べ物をせず自力で考えたコードを要約すると以下の通り。
上面に０個以上出っ張りの飛び出た、下面に０個以上穴ぼこのあいた２段で可能なものを全て作ります。
その２段から二つ選び（同じものを二つ選んでもよい）可能な4段全てを作ります。
4段でも同様に8段を作り、同じように8段を組み合わせて16段を作ります。
これを10＾10000段の直前まで作りつづけます。
つくった２倍段のブロックタワーは上下の凸凹以外で区別する必要がないので、上下の凸凹を主キーに値として組み合わせ数を保持すれば計算は意外とシンプルです。
10＾10000段を２進数になおしたときあるｎ桁目に１のビットが立ってたら、２^n段を作れた時にそれをどんどんアセンブリして積み重ねていけば答えが出ます
細部は覚えてませんが大体この方法で６時間半パソコンに計算させて正しい答えが出ました。
なぜ２段から計算を始めたかというと10＾10000を２進数になおしたとき１段単独からのアッセンブリーがなかったからです。
考えることが容易な２段から作った覚えがあります。
当時書いたときは１段から計算を始めるとプログラムが複雑になると考えてたようです。
例えば１０段を２進数で表すと1010段ですが、これは８段と２段を組みあわせれば１０段となります。
組み合わせた後、上面と下面にでこぼこのないセットの組み合わせ数を出力すれば答えとなります。
アセンブルするときに上面の凸凹が512通りのサブセット、下面の凸凹が512通りのサブセット、結合部の上面の凹凸が決まれば結合部下面の形が決まるので512通りのサブセット。
一つ結合するときにＢｉｇＯ(512＾３)、必要な段数は10＾10000=2^37000くらいなのでこの結合を３７０００回する必要があります。
BigO(512＾３*37000)の計算です。
当時コードを書いたときは試行錯誤の残る多少非効率で無駄も入ったコードも書いていた覚えもあります。
実際は上面と下面に制約があるのでもうすこし計算量が落ちてましたが、６時間半もパソコンを回したのを覚えています。
正しいコードだと、３０秒で答えが出るそうなのでもっと高度な発想が必要な問題だったようです。
正しい答えが出るからって計算に６時間半もかかっては不正解となったものでした。
ちなみに私は創価学会の方から小学校の足し算と掛け算までしかできない人間だとという悪いうわさを流されていますが。
本物の堀江伸一はこういう問題を趣味で解いている人間だったりします。
「堀江伸一さんだったら小学校の算数くらいだったら出来ますよ」
と窓全開はきはきした声で電話しうちまで聞こえてきた○○さんち。
多分創価学会女性陣は知らないと思うけど。
男性学会員は私を嘲笑うことを一生懸命楽しんでますよね多分。
http://www14.atwiki.jp/c21coterie/pages/597.html
さてこの問題を解くために昔書いたコードを見ると。
この問題はプロジェクトオイラーというサイトに掲載されている問題Ｎｏ324の問題なのですが。
とにかく自分で考えついたものを試しては駄目を繰り返しそのあとようやく答えにたどり着けた試行錯誤の跡が残りまくりの酷いコード。
どうしてこんな、意味不明で要領の悪いコードをたくさん書いたのだろう？
自分でも不思議。
この手の競技プログラムの問題に挑戦するたびに思うのですが。
今回はきちんとした答えにたどり着いていませんが（答えが出るまで時間かかりすぎ）。
正しい答えにたどり着けた問題で、問題を見返すとこんな簡単な考えで解けるのかと驚く問題が多いです。
答えにたどり着くと答えにたどり着くのに苦労した自分が不思議になる。
数回しかありませんがコード実行速度１位を取れたりした時は特に不思議な気分になります。
何故皆こんなシンプルな発想に気づかないのだろう？
そう思うこともあります。
多分この問題を正しく解いた人から私の発想を見るとなぜこんな頭の悪い発想で解いてるのだろうと思われてるのだと思いますが。
コード実行速度一位もあれだよな。
書いたときにはこれ以上早いコードは理論上ないだろと思って記述してネットで晒してんだけど。
後日見ると、抜かれてるってことがあったからな。
結局、真の一位ではなく、暫定一位なんだよな俺の場合、、、。
今回は私の思いついた方法は２倍段をつくって、条件に合うものが出来たら上に上にと積み立てていくだけ。
シンプルな発想なので実装に苦労した自分がいまみると無性におかしい。
シンプルな発想なのだからシンプルなコードが答えになるのに妙な技巧に走ってコードサイズが膨らみ自滅してる。
コードは間違ってないがナンセンスマシーンみたいにいらない処理がたくさんくっついてる。
今書きなおすなら。
dp[2][612][512]でブロックタワーの２倍段の組み合わせを動的計画法で求めるか。
最初の１段を再帰で求めて作って、あとは４重ループ。
一番外は約37000回、２倍段を作るループ。
その中に上面、下面、結合部面でブロックを結合する３重ループ。
それと、結合後、作ったブロックタワーを答えのためにアセンブリするコードも同じ要領で書くと。
アセンブリするコードと２倍段を作っていくコードは処理はほぼ共通だから、関数化すれば。
計算量は落とす方法は未だによくわからないが、今ならずっとシンプルに書けるなこれ。
すこしは勉強が進んでるのかもしれない。
