『フカシギの数え方』

『組み合わせ爆発』を分かりやすく説明する、やや恐ろしい動画があるので紹介する。

問題は「N×Nの格子状の道を同じ場所は通らずに左上から右下まで行く道順は何通りか」といった単純なものである。これに『最短経路で』と条件があれば学校で教えないタイプの算数で扱う問題だが、この条件が無いことで道順の数は大変なこととなる。これをお姉さんが少年と少女に教える、というのが動画の本筋である。

まず1×1では先に右に行くか上に行くかで2通り、2×2では12通り。3×3では早速184通りに膨れ上がり、4×4まではお姉さんが気合で数えて8512通りとなる。この時点でお姉さんは相当数え上げに長けたおそろしい逸般人だ。

5×5からはパソコン(2012年当時のもの)で数えるとすぐ出て約126万通り、6×6で数秒かかってざっくり6億。7×7では1秒で2000億通りを数え上げられるスパコンを持ち出してきて、4秒ばかりかかって約8000億通り。8×8では4時間かかって約3200兆通り。

さてここからがこの動画の恐ろしいところ。9×9の計算に取り掛かる時に『2,3日はかかっちゃうかもね 今日はお泊りだね！』などと楽観的な予想をするが、急に季節が巡る演出が流れ、2人が中学生になったところでお姉さんから電話がかかる。お姉さんの研究室に向かうとやややつれたお姉さんが、けなげにも6年半もの間無停止で動き続けた恐ろしいスーパーコンピュータを前に『4104京4208兆7026億3249万6804通り!めまいがしてきたわね!』と告げる。

次の10×10を数え上げようとするお姉さんに対しこれ以上は死んでしまうと忠告するものの、急に画風が変わり、分かっているけど止めないで、と感動のシーンとなる。お姉さんがエンターキーを押すとやけに壮大な風景が流れる。

25万年後、ロボットと化したお姉さんは25万年稼働し続けた恐ろしいスパコンから結果を受け取る。それを子供たちの子孫(25万年残せたのがすごい)に連絡するも、間違い電話とされて切られてしまう。それでも組み合わせ爆発を教える事しか能が無いお姉さんロボットは11×11の計算を行う...といったものである。

このことから、我々は計算量を少なくするアルゴリズムの重要性を学ぶことができる。

雑に言えばアルゴリズムへの入力サイズ(量や桁)をnとして、nが10倍になった時に計算量がnの二乗で100倍になるよりnそのままで10倍で済む方がよいし、log(10)nで1回増えるだけならもっとよろしいというものである。

これは余談だが、これの名場面を使ったラインスタンプが発売されている。元が短い動画だということもありやや使い勝手が悪いが、面白いので使える時は積極的に使っている。

あとこの『フカシギお姉さん』がアキネイターで出るか調べたところ、ちゃんと出た。1年近くプレイされなかったとのことでポイント稼ぎが捗ったことだ。