就活がつらいです(´・ω・`)最近はとくにエントリーシート提出の締め切りが続いていて本当につらい(´・ω・`)
だれか代わりに書いてくれないかしら。「エントリーシート代行会社」とかあればもうかりそう。最近は、塾通いや習い事で忙しい子供向けの「宿題代行会社」なるものがあるのだから、「エントリーシート代行会社」があってもおかしくないよね。世間は空前のベンチャー企業ブームらしいし、だれか作りませんかね――作りませんよねそうですよね。
ぐちはさておきそろそろ本題に入っていきます(現実逃避)
コードトライアスロンとは
コードトライアスロン……それは太古の昔より伝わる禁断の秘術……16世紀のはじめ、錬金術師パラケラススによって大成され、以降は《能力者》の一族にのみ伝えられてきたという……
――と冗談はさておき、「コードトライアスロン」はリクルートキャリア社が運営する「コード転職サイト」CodeIQの企画です。無料とはいえ会員制のサイトですのでここに詳しいことを書くことは控えておきます。詳しいことを知りたい方はCodeIQに登録しよう!(ステマ)
というわけで今日はわかる人だけにしかわからない謎の記事になっています。
提出コード
使用言語はRuby。2回目の提出で合格。primeライブラリは利用せず、実行時間は0.15秒でした。
感想と反省
提出コードを張り付けるだけでもよいのですが、自分自身の復習のためにも解答手順についてメモを残しておきます。せっかくのブログですし。
第1問
1問目はペラン数(フィードバックで知った)の問題。
提出コードの解き方としてはまずペラン数の第n項をとして、を次のように定義します。
これを直感的に理解しやすいよう、実際の数字を使って表にしてみます。
n | |||
---|---|---|---|
2 | 2 | 3 | 2 |
3 | 3 | 2 | 5 |
4 | 2 | 5 | 5 |
5 | 5 | 5 | 7 |
この表をよく眺めていると次のようなことがわかってくるはず。
これを実際のコードに落とし込んでやるだけです。
a,b,c = 2,3,2 (2..Float::INFINITY).each do |n| a # これが第n項目のペラン数 a,b,c = b,c,a+b end
第2問
第2問目は素因数分解の問題です。
自然数nの素因数は2からの間の素数にあらわれますが、必ずしも「素数生成→試し割り」という順番をとる必要はありません。実は2からの間の「整数」で試し割りをするだけで大丈夫です。
たとえばとして、実際に起こりうる過程を表に起こしてみます。
整数 | n | 素因数 | 試し割り後のn |
---|---|---|---|
2 | 60 | 2,2 | 15 |
3 | 15 | 2,2,3 | 5 |
4 | 5 | 2,2,3 | 5 |
5 | 5 | 2,2,3,5 | 5 |
この方法だと合成数(上記の例なら4など)が混ざってきそうな気もしますが、実際には起こりえないということが確認できました。
以上が提出コードでの考え方。ついで反省点ですが、大きく分けて2点。
この反省点を生かして該当部分を書き換えてみました。
def prime_division(num) factors = [] (2..Math.sqrt(num)).each do |factor| while num % factor == 0 factors << factor num = num / factor end break if num == 1 end factors end prime_division(p).last
第3問
第3問目はみんな大好き素数の問題です。
本問では素数の列挙が必要となります。そして素数列挙とくれば「エラトステネスのふるい」ですね。
ではまず「べた」に「エラトステネスのふるい」を書いてみましょう。
def erato(upper_bound) nums = (2..upper_bound).to_a primes = [] while nums[0] <= Math.sqrt(upper_bound) prime = nums.shift primes << prime nums.delete_if{|num| num % prime == 0} end primes + nums end
しかしこれでは列挙するまでに時間がかかってしまいます。しかも本問では最低2回は素数列挙を行わねばならないので、「エラトステネスのふるい」の高速化に取り組む必要があります。
というわけで上記の書き方では何が「ボトルネック」になっていたのかをあぶりだしていくと――
- 配列
nums
から先頭の要素nums[0]
を配列primes
に移しているのがまずい- ひとつの配列で完結する方法を考える
- とどのつまり「素数でないものをふるいおとす」のが「エラトステネスのふるい」の肝だから、合成数と確定したものを
nil
に変えていくというのはどうだ
Array#delete_if
はレシーバの要素すべてにブロックを実行するが、明らかにむだ- 整数iが合成数とわかった場合、次いで合成数と確定するのはである
Range#step
などを利用できないだろうか
以上の反省点をふまえてできたのが提出コードのような「エラトステネスのふるい」です。
def eratosthenes(upper_bound) nums = (0..upper_bound).to_a nums[0] = nums[1] = nil nums.each do |num| next unless num break if num > Math.sqrt(upper_bound) (num*2..upper_bound).step(num){|idx| nums[idx] = nil} end nums.compact end
――とここまであたかも自分で考えたかのように書いていますが、実は昔どこかで見たものの受け売り。ただ肝心の「元ネタ」がどこにあったのかを忘れちゃいました。てへぺろ(・ω<)。もしかしたらRuby以外のプログラミング言語で書かれた記事だったかも……
まとめ
提出した当時は解けたことに舞い上がっていたので、時間がたって改めて見てみると結構反省点が多いですね。世にいう「賢者タイム」とはこのことかしら。
ちなみに以下が反省点を生かして書き直したコードです。今の自分にとっては最善のコードですが――将来の自分が見たらどう思うことやら。「将来このコードを見て不出来を恥じる」そうなるよう勉強していきたいと思います。