やねう企画2005年入社問題解答と解説 - やねうらおブログ(移転しました)

やねう企画2005年入社問題(id:yaneurao:20050929)の解答と解説。

問1.
f(x,y)が数学的関数(要するに、x,yが定まれば値がひとつ定まる関数)であることは見れば気づくはず。fの再帰停止条件はx==1 || x==yで、この時の返し値は1。よって、g(a) = bだとしたら、少なくともfはb回呼び出されていることを意味する。この呼び出し回数をどうやって減らすのかというのがひとつ目の着眼点。

fの呼び出しを減らす方針は二つある。

ひとつはf(x,y)をstd::set等でmemoize(→http://www.kmonos.net/wlog/52.php#_0308050827)して、計算オーダーが減ることを証明する。実際、このことにより計算オーダーはPN→Pになるのだが、そのへんは割愛。

もうひとつは、手動でinline展開をしていく方法。うまくinline展開していけば、g(n)= $2^{n-1}$ まで導ける。再帰の展開(非再帰への書き換え)については、問2と絡むので、そちらで詳しく解説する。

また、fの定義を見れば、組み合わせの数(高1の数学で出てくるコンビネーション)と同じ定義だと気づく。だから、f(x,y) = C(y-1,x-1)を直接導いていた人も居た。

あるいは、f(x,y)が数学的関数であることから、fのx,yの値が小さいときについてfの値を表にしてみると、これがパスカルの三角形(→http://www.nikonet.or.jp/spring/sanae/MathTopic/pascal/pascal.htm)上の係数であることに気づくはず。(パスカルの三角形は同時に無数の等式を満たす非常に魅惑的な三角形であり、斜めラインにフィボナッチ数列が出てきたりするのが興味深い。)

fがC(y-1,x-1)まで導けていて、そこから一歩抜け出せない人が多かったが、パスカルの三角形は、 $(x+y)^n$ を展開したときに出てくる係数である。g(N)はこの三角形の1段をまるまる足した数である。すなわち、g(N+1)= $\sum_{i=0}^{N} C(N,i)$ で、この右辺は $(x+y)^n$ を展開したものにx=y=1を代入したものだから $(1+1)^2$ とわかる。すなわち、g(n+1)= $2^n$ である。

もしくは、g(1),g(2),..を実際に書き出してみれば、1,2,4,…と等比数列になっていることから、これを証明することを考えれば良かったと思う。g(n)=2 g(n-1)を証明するのはg(n)とg(n-1)の項を実際に書き出してみれば簡単だ。

もしパソコンの前でこの問題を解いているならば、“最適化しなさい”という問題なので、最適化前のgと最適化後のgとの関数の値が小さな数字(特に、N=1,2,3)ぐらいで成り立つかどうかはチェックしていなければならない。printf("%d == %d",old_g(n),new_g(n));のようなチェックは当然なされているべきであり、それをやって一般項に気づかないというのはありえないから、fが導けていてgが導けていないのはこの手のチェックを怠っているとしか思えない。

そんなわけで正解は



int main() { return 1 <<(100000-1); }

となる。2倍するループや、powを使って書いてきている人も居たけれど、ビットシフトが一番簡単だろう。

ここからは余談。

この問題を作ったあとで、この問題におけるfを作表したものが出てくる書籍を見つけた。Knuth先生の「コンピュータの数学」(→ASIN:4320026683。ちなみに原書は「ConcreteMathematics」であり、離散数学の本である)だ。私の大学時代にこの本が発売になって、駅まで自転車で1時間かけて立ち読みしに行った覚えがある。でも難しくてゼンゼン意味がわからなくて毎日その難しさにうちのめされながら自転車で1時間かけてまたとぼとぼと帰ってくるという日々が続いた。「もう万引きしてやろうか」と何度も思いながらも、「こんな分厚い本の入る鞄、持ってないしなぁ..」とか思いながら悶々と過ごす日々であった。たかだか9,450円の本で、いまなら、仮にこの本が94万5千円だとしても買うと思うけれど(私にとっては、それくらいの思い入れのある本なので)、当時はその9,450円すらなかったのだ。

もう10年以上前の話で、本の内容はすっかり忘れていたのだけど、問題を作るときに無意識に出てきてしまったようだ。ちなみに、この本は私は社会人になって初任給で買った。いまは私の書庫に大切に保管されている。この本自体は絶版寸前だが、プレミア必至なので持っていない人は買うといいと思う。