はじめに

こちらの記事

のScheme版を書いている。途中、ダブリングについて調べていたところ長くなったので別記事にまとめてみた。

ダブリングについては元記事が参照している解説記事はあまり自分にはピンと来なくて探し回った結果、下記のサイトが役に立った。感謝。

スライドでアルゴリズムが可視化されているのでわかりやすい。まずはこちらで基本を押さえた。

実際にコードを書く際にはこちらを参考にした。

なお関数が合成可能であるという基本的な性質に関してはこちらの記事が言及している。

関数が合成可能、という性質はそのまま「ある入力に対して出力が変わらないことが保証されている」ということでもあり、これはもし繰り返しの途中で以前出てきたのと同じ入力値が出てきた場合は、必ず同じ道をたどる、つまりループするということでもある。ダブリングを使う問題はループを見つけ出せばより効率的に早く解ける可能性があり、プロコンでダブリングでないと解けない問題が出されにくいというのはループを見つけ出す手法に帰着してしまうからではないだろうか。

アルゴリズムスニペット

ダブリング

※準備中

ループを含む経路探索

※準備中

ABC-167-D問題-Teleporter

ダブリングについて理解したのでひとまずSchemeで例題を解いてみた。

……見事にTLEしていますね。時間計算量もメモリ使用量もどちらもO(NlogK)なので厳しいのかな。この例題ではNの最大値は2x10^5、Kの最大値は10^18なので、NlogKは最悪ケースで約12,000,000になってしまう。

この問題については「素直にテレポート先を辿りループした時点で探索を打ち切り、(K-(ループするまでの道中にある町の数))の(ループ中の町の数)を法としたmodを取り、最終的なKステップ目の町を求める」というループを見つけ出す手法で解いた。

AOJ-NTL_1-Power

繰り返し二乗法の問題だが、Gaucheにはexpt-modという便利な関数があって、最悪ケースでも間に合ってしまう。

(use gauche.time)
(time-this 1 (^() (expt-mod 100 1000000000 1000000007)))
;  => #<time-result 1 times/  0.016 real/  0.015 user/  0.000 sys>

気になったのでexpt-modの実装を覗いてみる。

; C:\Program Files\Gauche\share\gauche-0.97\0.9.9\lib\gauche\numerical.scm

;; modulus exponent
(define (expt-mod n e m)  ; (modulo (expt n e) m)
  (if (and (exact-integer? n) (exact-integer? e) (exact-integer? m) (>= e 0))
    (if (< (* (integer-length n) e) (fixnum-width))
      (modulo (expt n e) m) ; in fixnum range, it's fast enough
      (let loop ([b (ash 1 (- (integer-length e) 1))]
                 [r 1])
        (cond [(zero? b) r]
              [(zero? (logand b e)) (loop (ash b -1) (modulo (* r r) m))]
              [else (loop (ash b -1) (modulo (* (modulo (* r r) m) n) m))])))
    (modulo (expt (inexact n) e) m))) ; inexact fallback

やはり繰り返し二乗法を使った実装だった。

※AOJはSchemeで回答できないのでパス。

ABC-13-D問題-阿弥陀

これもあみだくじ1個分が合成可能な関数fになっていて、D個連結することでどういう関数になるか、を計算する問題になっている。もちろんD個の関数の出力をそれぞれを見ていくとどこかでループする。

この問題の最悪ケースではO(NlogD)がNの最大値2x10^5、Dの最大値10^9から6,000,000なのでダブリングだとギリギリTLEしないくらいだろうか。もちろんあみだくじ1個分の計算はしなければならないのでここに2x10^5本の横線の処理が必要になってくる。

なおこの問題はダブリング、ループを見つけ出す方法どちらでもTLEしてしまった。これがSchemeの処理性能の限界なのか、それとも自分のSchemeレベルが足りないせいなのかはよくわからないが、残念な結果……。

ダブリングでの回答
- https://atcoder.jp/contests/abc013/submissions/23806492
ループ経路探索での回答
- https://atcoder.jp/contests/abc013/submissions/23805625

ループ経路探索の場合はメモ化で高速化する汎用的に使える関数まで用意したのだが無念だ……。

ABC-179-E問題-Sequence Sum

ダブリングで解くなら、用意するダブリング配列の長さをMと置くのだろうか？　だいぶ非効率な気がしなくもない。

この問題はループ経路探索の方法で解いた。

途中の経路に出てくる数Ai（＝ノード）が全て必要になるわけだが、先に作った汎用ループ経路探索関数からコピペしてきて改変することで割と簡単に書けた。こういう点でもスニペットは大事なんだな。

(define (answer o)
  (format #t "~A~%" o))

; --------------------------------------------------------------------------------

; straightの先端ノードから始めてstep目までのノードの数の合計を返す
(define (sum-nodes straight circle step)
  (cond [(<= step (length straight))
         (apply + (take straight step))]
        [else
          (+ (apply + straight)
             (* (apply + circle) (quotient (- step (length straight)) (length circle)))
             (apply + (take circle (modulo (- step (length straight)) (length circle)))))]))

(let* [(N (read))
       (X (read))
       (M (read))]

  (let* [(cache (make-hash-table))]
    (let loop [(idx 0) (now X) (past-nodes '())]
      ; past-nodesが長くなりすぎるとリストへのfindの性能が落ちるので
      ; すでに訪れたノードの情報を入れるキャッシュとしてhash-tableを使う
      (if-let1 dupe-idx (hash-table-get cache now #f)
               (let-values [((straight circle) (split-at (reverse past-nodes) dupe-idx))]
                 (answer (sum-nodes straight circle N)))
               (begin
                 ; 今いるノードをキャッシュに詰めて次のノードへ
                 (hash-table-put! cache now idx)
                 (loop (+ idx 1) (expt-mod now 2 M) (cons now past-nodes)))))))