みなさんこんにちは、開発スタッフのCHOです。

去る10月23日、弊社がスポンサーとしてご協力しているプログラミング競技PG BATTLE 2021に参戦してきました。PG BATTLEは企業・学生対抗で3名1チームを結成し、各メンバーが「ましゅまろ」「せんべい」「かつおぶし」のどれかの問題に挑戦し、正解数と速さを競う競技です。

私は最も難しい問題が出題される「かつおぶし」担当となっていました。

問題は全部で4つあり、それぞれの問題に1~6の難易度が設定されています。「かつおぶし」は難易度3~6が各一問ずつ出る場合が多く、私の作戦では難易度5である第3問目までチャレンジしようと思っていたのですが、当日蓋を開けてみるとなんと3問目と4問目の両方が難易度6になっているという予想外の自体が発生。結局、最初の2問しか解けませんでした。さらに、解けたとは言っても最初の1問目から「離散的」という常識から外れた問題が出題されてピンチ。苦戦した結果私は独自の「噓解」で解いてしまいました。

具体的に、どんな問題をどう解いたのか説明してみたいと思います。少し専門的な話になりますがお付き合いください。

問題文はhttps://products.sint.co.jp/q_list_2021に掲載されていますが、要約すると「Nの階乗の10進表記の桁数を導く」問題といえるでしょう。ただし、「Nは50万まで」とされており、普通の64bitの整数は勿論格納不可能です。自前で大きい整数型を実装するという手を思いつきましたが、掛け算だけで計算量がO(N^2)を超えそうで難しいと判断しました。さらに、「階乗の結果の最上位桁に1と9が含まれない」という複雑な条件が付いており、すぐに自信を持って解答のアイデアを出せませんでした。

結局、私は1からNまでの連続した掛け算の中、常に上位12桁の結果を保持して、下の部分を切り捨て別途に余った桁数を記録するという実装を提出しました。結果としては無事正解となったものの、最上位桁条件を如何に活用できるかについて手がかりが見つけられなかった点が非常に気がかりでした。

正解を見てみると割と素直に解けること、そして活用しなかった条件の意外な使い方に驚きました。

各1≤i≤Nに対してlog10を取った結果を足し合わせて、更にその整数部分を取れば10進表記の桁数になるが、各log10(i)に誤差があるため、累積された誤差によって桁数が間違う可能性があります。そこに効いてくるのが先述の条件「階乗結果の最上位桁に1, 9が含まれない」です。何故かと言うと、log10は約10^-15の相対精度を持ち、故に各log10(i)の絶対精度は10^-7の保証があると分かります。その結果、最大50万個のlog10(i)を足し合わせた結果は少なくとも0.05の絶対精度を持ち、条件にN階乗の最上位桁に1と9が含まれないので、0.1の誤差範囲内では桁数が変わらなく問題ないということでした。

限られた時間の中でしたので、当日は「噓解」でもとりあえず通ってラッキー程度に思っていましたが、振り返って考えると、正解と同じように最上位桁条件のおかげで切り捨ての誤差が問題に至らなかったのでしょう。というわけで、今回は「嘘解」がありつつも挑戦したPG BATTLEについて書かせていただきました。

今年は弊社がスポンサーとなったご縁からお祭り気分で参加させていただきましたが、成長意欲豊富なエンジニアと競いあうことができるPG BATTLEに参加できたことで、エンジニアとして大変いい刺激を受けました。是非来年もPG BATTLEに参加し、今年よりいい結果が出せるよう日々勉強を重ねていきたいと思います。改めて、ご参加された皆様大変おつかれさまでした。また、この記事を読んで興味を持ったという方がいらっしゃれば、来年は良きライバルとして是非切磋琢磨できるのを楽しみにしています。

ここまでお読み頂きありがとうございました。また次回の記事でお会いしましょう。