「1000のアルゴリズムを持つ男」vs.「やわらか頭脳」：最強最速アルゴリズマー養成講座（1/3 ページ）

典型的なアルゴリズムをたくさん知っている人間が最強か――？　いいえ、典型的なアルゴリズムを知らなくても、違ったアプローチで答えに迫る方法はいくらでも存在します。短い実行時間で正確な答えを導き出せるかを考える習慣をつけましょう。

典型的なアルゴリズムに捕らわれない思考

　アルゴリズマー養成講座と銘打ってスタートした本連載。もしかすると読者の方の興味は、はやりのアルゴリズムや汎用的なアルゴリズムを知ることにあるのかもしれません。しかし、今回は、いわゆる「典型的なアルゴリズム」を用いずに進めていきたいと思います。

　なぜ典型的なアルゴリズムを用いないのか。それは、典型的なアルゴリズムばかりを先に覚え、それだけでTopCoderなどを戦っていこうとした場合、それに少しでもそぐわない問題が出た場合に、まったく太刀打ちできなくなってしまうことを避けるためです。

　第一回の連載でRedCoderの実力について触れましたが、筆者の肌感覚でレベルを表すと、小学生までの算数の知識で解ける問題をこなすことができればYellowCoderに、中学生までの数学の知識で解ける問題をこなせればRedCoderになるのはそう難しいことではありません。しかし、現実はそうではありません。数十万人が登録しているTopCoderですが、RedCoderはたった数百人しか存在していないのです。これはなぜなのでしょう？

　答えは簡単です。小・中学生までの知識で十分に解ける問題でも、どう解くかを思いつかなければ、その問題を解くことができないからです。ここまで書けばお分かりかと思いますが、問題を解く上で必要なのは、“柔軟な発想力”であり、“有名なアルゴリズムを詰め込むこと”ではないのです。

　TopCoderのような技術コンテストでよい成績を収めても実際には役に立たない、といった見解を持っている方も多いかと思いますが、ここまでお読みになった方であれば、それが誤解であることにすぐに気づくでしょう。大会で培った柔軟な発想力は、原則として会社での開発などにも大きく役立つのです。もしそうでないとすれば、それは発想力を必要としない単純作業に従事している可能性を疑った方がよいかもしれません。

　もちろん、筆者は典型的なアルゴリズムを知ることを否定しているわけではありません。実際、こうしたアルゴリズムを知っていることが有利に働く場面は多々存在しますし、発想の手助けになることもあります。ある段階では、こうしたアルゴリズムを覚えていくのも大切でしょう。今後の連載ではこうしたアルゴリズムについても扱っていく予定ですが、まずは、それらに頼らず、どうすれば短い実行時間で正確な答えを導き出せるかを考える習慣を身につけていくとよいでしょう。柔軟な発想というのはそうした思考から生まれてくるものです。

アルゴリズムの迷路に入り込まないために

　ここまで述べてきたことをTopCoderの問題で証明するために、少し古い問題ですが、TopCoderOpen 2008 Qual Round 1に出題されたEasy問題を取り上げたいと思います。

　問題は以下のような内容です。

人間が1人、モンスターがM匹、ウサギがB匹います。ここから、モンスターか人間がいなくなるまで無作為に2匹（もしくは1人と1匹）を選び出し、以下の行動を繰り返します。

• モンスターとモンスターが選ばれると、両方のモンスターが死にます
• モンスターとモンスター以外が選ばれると、モンスター以外が殺されてしまいます
• ウサギとウサギが選ばれると、何も起こりません
• ウサギと人間が選ばれると、人間の生存確率が最も高くなるように、ウサギを殺す、またはそのままにする、のどちらかの選択をします

モンスターの数Mとウサギの数Bが与えられたときに、最後に人間が生き残る確率を答えなさい。ただし、M、Bともに1000以下の整数とする。

　この問題を典型的なアルゴリズムで解こうとすれば、動的計画法を用いて、モンスターが何匹、ウサギが何匹残っているときに生存確率がどれくらいかを下から順番に計算していけば、求めることができます（この方法自体がそもそも分からない人は、後の連載の別の問題で紹介しますので、ここでは読み進めてください）。ただし、10行以内で書ける人はそうはいないのではないかと思います。

　ここではあえて答えは書きません。ですが、この問題は、少し柔軟な発想ができれば、2行程度のプログラムであっさりと解くことができます。プログラミングがまったくできない方でも解ける問題ですので、ぜひ挑戦してみてください。

　上記の問題はほんの一例ですが、典型的なアルゴリズムを知らなくても、違ったアプローチで答えに迫る方法はいくらでも存在します。むしろ、そうした方法の方が効率が良かったり、単純であったりすることもあるのです。実は上記の問題も、2行で表すことができるにもかかわらず、正答率は26％程度と非常に難易度の高い問題となっています。いかに発想力が重要であるかは、こうした例からも示すことができると思います。

積み上げるのは“知識”よりも“経験”

　さて、ここまでで「問題を解く上で必要なのは“柔軟な発想力”であり、“有名なアルゴリズムを詰め込むこと”ではない」と述べてきました。それでは「柔軟な発想力」というものはどうすれば身につくのでしょうか？　これは非常に難しい命題であり、意見が分かれるところでもありますが、ここでは筆者の見解を示します。

　柔軟な発想とは何かを考える前に、「発想」とはそもそも何なのかを考えてみましょう。筆者は「発想」とは、「経験から一歩先のアイデアを導き出すこと」だと考えます。どんなに才能豊かな人物であっても数字を知らなければ計算はできませんし、生まれたばかりの何も知らない状態では言葉を話すことはできません。これと同じく、経験がなければ、問題を解くための発想が出てくるはずがないのです。経験は単なる知識を凌駕するのです。

　それでは結局のところ、典型的なアルゴリズムを詰め込んでいくしかないではないか、と思う人も多いでしょう。しかし、それは違います。まったく経験をせずに、単なる“知識”として詰め込んだものは、現実にはほとんど役に立ちません。例えば、高速フーリエ変換の仕組みだけを突然教えられたとして、「これは多倍長整数の乗算の高速化に使える！」と発想できる人がどれだけいるでしょう？　要するに、訳の分からない知識をいきなり詰め込まれても、実際にその知識を使ってそれがどう凄いのかを体験しない限り、その知識を活用することはできない、ということです。

　そして、経験というのは、さまざまな場面で積むことができます。TopCoderのような大会しかり、趣味・仕事などで行っている開発、情報系とあまり関係ない数学ないしは算数の問題の経験なども、関連性の大小はあるものの、十分にここでいう経験に当てはまるものです。

　こうしたコンセプトに基づいて本連載は書き進めていますので、実際にコードを書いて、経験をする、といったことを強く推奨します。TopCoderの過去問題というのは、あの手この手で参加者を悩ませようとしているため、さまざまな経験を積むのに適しています。可能な限り自力で考え、自らの答えを出してから解説に入るのがよいのですが、それができないにしても、自分で方針などを考えた後に解説を読むのと、何も考えずに解説を読んだのでは、得られる経験は大幅に変わってきます。また、解説を読んだ後に書かれたソースを写したり、別の言語で書き換えたりするだけでも、大きな効果が得られると考えます。

　以下のページから今回の問題に移りますが、ぜひとも上述したようなことを意識しながら読み進めていただけると幸いです。