読者です 読者をやめる 読者になる 読者になる

nekoTheShadow’s diary

技術ブログとして始めたはずが、読書&愚痴ブログになりました(´・ω・`)

CodeIQ「カット・アンド・スクエア」に参加しました。

 就職活動が落ち着いてきたとはいえ、まだばたばたはしているので、簡単にまとめておきます。正直なところ、いろいろ書かねばならないほどのことはしていませんし。あとは「8月序盤で就活落ち着いちゃまずいでしょ」というのもいいっこなしで(現実逃避)。

 直面中のつらい現実はさておき、提出コードは以下になります。使用言語はRuby。最初の提出で合格でした。

 「Don't Repeat Yourself? 何それおいしいの?」状態のコードですね。一応は同じような処理をまとめてメソッドにすることは考えてみたものの、引数にProcを渡したりせねばならず、それではかえってわかりづらいと判断、結果としてコピペプログラムが出来上がったわけです。言い訳乙。

 さて模範解答では2次方程式を利用して解くことが求められていたようですが――まったく思いつきませんでした。「浮動小数点を利用することに日和って採用を見送った」とかではなく、純粋に気づきませんでした。そういうわけでまったく別のやり方をひねり出すことになります。

 求める整数をT、その前半部と後半部をそれぞれI、Jとすると、T = (Iの2乗) + (Jの2乗) となります。ここでTの下mけたに関して、(Iの2乗)と(Jの2乗)の下mけたが決まれば、自動的にTの下mけたも決まります。また(Iの2乗)と(Jの2乗)の下mけたに関しても、IとJの下mけたが決定すれば、同じように決まります。すなわち、IとJの下mけたがそれぞれわかれば、Tの下mけたは自動的に確定するのです。ここで設問の条件より、Tの下mけたはJの下mけたとまったく同じですから、IとJを下位のけたから確定させていく際、(Iの2乗) + (Jの2乗)の下mけたがJの下mけたと一致しないものを振り落していけば、計算量が抑えられる。そういう算段でした。

 もちろん模範解答とかけ離れているだけあって(?)、問題点も多いアルゴリズムです。なかでも1番の問題はnが増えるごとに計算量が爆発的に増えていくこと。nが1増えるたびに10倍かそれ以上の計算が必要になってきます。つまりnが大きいと計算量が多くなりすぎて、使い物にならない可能性が高い。正直にいって、わたしが正解を導けたのはたかだかn = 10程度だったから。もしn = 20とかであれば、間違いなく答えを出すことはできなかったでしょう。

 要はラッキーだったということで。この幸運が就活にもあればよかったのに……(´・ω・`)