CodeIQ 「タンジェント・フラクション」問題解答コード
CodeIQ問題の解答公開記事です。
codeiq.jp
問題の概要
今回は以下のような問題でした。
方針
この問題を解くためには、以下の三角関数の公式を使います。
題意から、はそれぞれ単位分数となるので、を自然数とした時に、それぞれとあらわす事が出来ます。これを先の公式に当てはめると、
となります。
というわけで、を満たし、且つ右辺が単位分数になるような自然数の組み合わせの数を算出すれば良いと言う事になります。
解答コード
こちらが提出したコードになります。
class Codeiq3182 def solve(m) cnt = 0 tan_m = Math.tan(m) max_b = (1 / Math.tan( m / 2.0 )).to_i (2..max_b).each do |b| i=((b**2 -1).to_f / (2 * b).to_f).ceil (i..(b-1)).each do |n| (a, r) = ((n*b) + 1).divmod(b-n) next if (r != 0) tan_ab = (a + b).to_f / ((a * b) -1) break if(tan_ab < tan_m) cnt += 1 end end return cnt end end puts Codeiq3182.new.solve(gets.to_f)
が単位分数になるので、を自然数とした時に
が成り立つ自然数の組を求める方法で解いています。
上記の式を組み変えると、になるので、右辺を実際に計算して余り0になるの組み合わせの数をカウントしてます。
の値を定義した時、の値が計算上1以上になるようにの初期値を調整しているのが、工夫といえば工夫なのかもしれません。
感想とか
三角関数とか使うのは学生時代以来なので、最初は問題の内容を理解するだけでいっぱいいっぱいでした(><)
記事ではさらっとの公式を書いていますが、実際はかなり数学の解説サイトをググって調べてきたものです。もはやこのへんの公式とかは、頭の中からすっぽり抜け落ちてしまってますなー。。
また、今回の解法もかなりしらみつぶし的なやり方で解いているので、もう少し効率の良いやり方があるのかと色々考えては見ましたが、現状ではこれが精一杯ですw
実行速度は、まだまだ改善の余地はありそうですね。