徒労

Problem 71。分母が100万未満の既約分数を小さい順に列挙したとき、3/7 のすぐ前に来るものを求めよという問題。

ネタバレ注意。
前からずっと使いたい使いたいと思ってたけど機会の無かった Stern-Brocot 木を引っ張り出して実装した。Stern-Brocot 木とは、以下の通り非常に単純な再帰式で定義された無限に深い二分探索木で、この簡単な定義にも関わらず既約分数全てを列挙して、しかも既約分数だけを列挙するという優れものなのです。既約分数を O(log n) で探したいときはこれ!

import Data.List
import Data.Ratio

stern_brocot = rec (0,1) (1,0)
    where rec l@(a, b) r@(c, d) = Tree (rec l mid) (uncurry (%) mid) (rec mid r)
              where mid = (a+c, b+d)

find_path q (Tree l s r) = case compare q s of
                             LT -> 'L':find_path q l
                             EQ -> []
                             GT -> 'R':find_path q r

follow (Tree l s r) 'L' = l
follow (Tree l s r) 'R' = r
tred_path (Tree l s r) [] = s
tred_path tree (c:cs) = tred_path (follow tree c) cs

path_to_37 = find_path (3 % 7) stern_brocot
solve d = find (stop . snd) $ zip trail (tail trail)
    where stop (Tree l s r) = denominator s >= d
          trail = scanl follow stern_brocot (path_to_37 ++ 'L':repeat 'R')

この木、他にも何に使うかさっぱりわからん面白い性質が沢山ありまして、いつか何かに使ってみたくてたまらなかった代物でして。しかも実際のところ使い道が殆ど無いので機会に恵まれなかったこともあってこの解答を書けたことで大満足したのでした。

解答者の集まる掲示板より:

999999 って 7 で割れるから 3/7 の分母 999999 に直して分子から 1 引きゃいいじゃん。

orz