脳log[20240109]

2024年01月09日 (火) [AtCoder] Stern-Brocot 木の名前を最初に目にしたのはこのとき。「格子点の数え上げの高速化 - memo」(リンク切れ)。ABC172-D「Sum of Divisors」に関連してだった>20200628p01.06。最近では ABC333-G「Nearest Fraction」に関連して目にしたし耳にした。たまたま今日ページをめくっていた『コンピュータの数学』の 116 ページにも名前と、具体的な木の図と操作が載っていた。その操作はこのときの驚きとともに覚えている。「なにこれ！ 分数を初めてならった小学生が必ず間違える分数の足し算(通分せずに分母どうし分子どうしを加算する)にこんな意味があるとか！」 Project Euler の Problem 71 Ordered Fractions に関連してだった。「Project Euler Problem #71 | KeyZero Conversation」 ここでのキーワードは Farey sequence (en.wikipedia.org) だったけど、See also のセクションに Stern–Brocot tree (en.wikipedia.org) の名前を見つけた。そうと知らず 10 年以上前に出合っていたのだ。でもまだ木については知らないし使えないよ。だけど何回も目にするうちに怖くはなくなってきたかな。たかだか数年前まではフィボナッチ数列も謎の怖い存在だったのだ。「フィボナッチ数？ 「競プロ典型 90 問」でも見かけたが、この数列がどうして頻繁にあちこちに登場するのかわからない。限りなくありふれたジェネレータなのか」 外国人の名前を付けるのが概念を謎のベールで覆ってしまって良くないと思うな。それがただの名前であり他と識別するための符号に過ぎないことさえ明らかではなくなってしまうのだから。■■■精進。ABC333-G「Nearest Fraction」。さっきリンクを張った動画によるとこの問題が「あなたは Stern–Brocot 木を知っていますか」という問題だったらしいので、最初の１問にちょうど良いかと。■提出 #49175972 (AC / 577 Byte / 125 ms)。実装中に聞こえてきたので TLE を出す前に動画の通りに二分探索で対策してしまった。あと分母が10進11桁と19桁になる２数の差と差を比較するのに何ビット必要になるかという話題も聞こえてきた。30桁の差と差を比較するのに60桁200ビットを普通は要するのではないか。もちろん GCD の分だけ減るがどれだけ減るかはわからない。普通でない方法は知らない。だから WA を出す前にこちらも必要な対策をしてしまった。入力は文字列として受け取って分子分母を分けて扱い、出力前の比較では Rational を使った。■最も新しい C++ での提出 #49139061 に普通でない方法がひとつ見られる。比較結果が 10**18 未満になるような式をまず用意して、その値をある素数の mod で求めて(式の途中の値が３数の積(10進60桁まで)になるから)、２つの素数でそれをすると中国剰余定理で実際の式の値が復元できるみたいな？ コメントに全部書いてあるんだけど、「Since p/q - a/b < c/d - a/b = 1 / bd」の左辺が 1/bd より小さくなる部分がわからない。いや……わかった。そうかと思ってさっき見たときは比較するものを間違えていた。もういちど 116 ページにある木の図を確認したら、隣接する２つの分数は差が 1/bd になっていた。「なっていた」ではなくいついかなる場合でもそうなることを示して理解しろって話ではあるんだけど、つまりそうなるような操作をしているはずなんだけど、ぼんやりなので操作と結果が繋がりません。■本読みを再開したら、差が 1/bd になることが次の 117 ページに書いて示してあった。■「２つの素数」っていうのは、かつて AtCoder でよく見られた 10**9+7 と、もうひとつは 10**9+9 が使われていた。あれって双子素数だったんだ(知らなかった)。どちらも 10**9 をちょっとだけ超える数だから、掛けると 10**18 を超えるけど 60 ビットは超えないみたい。使い勝手のいい数だ。