1. 問題 — いろはちゃんとマス目
縦 マス、横 マスのマス目がある。左上のマスを出発点とし、右または下に 1 マス移動することを繰り返して右下のマスへ到達する経路の総数を求めよ。
ただし、下から 個以内かつ左から 個以内のマスには移動できない。答えは で割った余りを出力すること。
入力形式
H W A B出力形式は、移動方法の数を で割った余りを 1 行で出力せよ。
D – いろはちゃんとマス目
2. どこで切り替わるか場合分け
マス目の中で進めない部分は左下に固まっています。
1〜Bまでは、高さ H-A で、
B+1〜Wまでは、高さ H になっています。
そこで、どのタイミングで高さが変わる領域に移るのか、で場合分けすることにしました。
左上を(1, 1)、右下を(W, H)として、(x, y)で位置を表します。
x が B から B+1 に進むのは、各パターンで一回だけなので背反です。
この位置は、y は 1〜H-Aまでです。
このときの条件付き場合分けは、(1,1)〜(B,y)まで場合数と(B+1, y)〜(W, H)までの場合数をかけたものになります。
;; x, y from 1 to W, H
(defun go-right-at-B-y (H W A B y)
(declare (type fixnum H W A B y))
(cond ((<= 1 y (- H A))
(mod-round (* (combi (+ (1- B) (1- y)) (1- y))
(combi (+ (- W B 1) (- H y)) (- H y)))))
(t 0)))
Code language: Lisp (lisp)すべての場合は、これを合計します。
(defun pattern-not-go-under-A-B (H W A B)
(declare (type fixnum H W A B))
(loop for y from 1 to (- H A)
with result = 0 do
(setf result (mod-round
(+ result (go-right-at-b-y H W A B y))))
finally (return result)))
Code language: Lisp (lisp)検算用のテストケースを作りました。
(progn
#+swank
(progn
(ql:quickload :parachute)
(parachute:define-test test-cases
(parachute:is = 2 (go-right-at-b-y 2 3 1 1 1))
(parachute:is = 0 (go-right-at-b-y 2 3 1 1 2))
(parachute:is = 2 (pattern-not-go-under-a-b 2 3 1 1))
(parachute:is = (* 1 3) (go-right-at-b-y 3 4 1 2 1))
(parachute:is = (* 2 2) (go-right-at-b-y 3 4 1 2 2))
(parachute:is = 0 (go-right-at-b-y 3 4 1 2 3))
(parachute:is = (+ 3 4) (pattern-not-go-under-a-b 3 4 1 2))
(parachute:is = 3570 (pattern-not-go-under-a-b 10 7 3 4))
(parachute:is = 1 (pattern-not-go-under-a-b 100000 100000 99999 99999))
(parachute:is = 738162020 (pattern-not-go-under-a-b 100000 100000 44444 55555))
)
(parachute:test 'test-cases)))
Code language: Lisp (lisp)2つのprognで囲っているのは、pareditでフィーチャーフラグごと一括キルして移動できるようにするためです。
2.1. mod計算と割り算
さて、問題は、この場合分けをどう計算するかです。
というのも、そのまま計算すると繰り返し回数も値も大きくなるからです。
値については、剰余で丸めるようになっています。
(defparameter *mod* (+ (expt 10 9) 7))
(defun mod-round (n)
(mod n *mod*))Code language: Lisp (lisp)問題は、場合の数の計算です。
はじめは、このようにnCrを計算しました。
(defun combi/first(n r)
(declare (type fixnum n r))
(loop for a fixnum from n downto 1
for b fixnum from 1 to r
with result fixnum = 1 do
(setf result (mod-round (/ (* a result) b)))
finally (return result)))
Code language: Lisp (lisp)nから下がって掛けつつ、1から上がって割れば、常に割り切れるので、うまくいくと思ったからです。
しかし、この方法はmodの剰余を超えると、実は割り切れずエラーになります。
整数の「掛け算」と「mod（剰余）」だけなら、順序や回数を変えても最終結果は同じですが、整数除算はそのまま扱えないからです。
2.2. モジュラーの逆元（mod-inv）
このときに使うのが、modular inverse（法 における掛け算の逆数）です。
今回、*mod* (+ (expt 10 9) 7)は素数なので、逆元はフェルマーの小定理（Fermat’s little theorem、素数法でのべき乗による逆元計算）で求められます。
(defun mod-pow (base exp)
(loop with result = 1
with b = (mod-round base)
with e = exp
while (> e 0)
do (when (oddp e)
(setf result (mod-round (* result b))))
(setf b (mod-round (* b b)))
(setf e (ash e -1))
finally (return result)))
(defun mod-inv (n)
(assert (/= (mod-round n) 0))
(mod-pow n (- *mod* 2)))Code language: Lisp (lisp)これを使うと、(mod-round (/ (* a result) b) を(mod-round (* a result (mod-inv b))) とすればよいことになります。
一応、ハッシュテーブルで計算結果を再利用するようにしてみました。
(declaim (ftype (function (fixnum fixnum) fixnum)
combi/cache))
(let ((cache (make-hash-table :test #'equal)))
(defun combi/cache (n r)
(declare (type fixnum n r))
(let ((rr (min r (- n r))))
(cond
((gethash (cons n rr) cache))
(t (loop for a fixnum from n downto 1
for b fixnum from 1 to rr
with result fixnum = 1
do (setf result
(mod-round (* a result (mod-inv b))))
finally (return
(setf (gethash (cons n rr) cache)
result))))))))Code language: Lisp (lisp)3. 階乗の効率的な計算
ところが、この方法でもまだ時間がかかっていました。
最後のテストケースが答えが出てこないのです。
計算結果を無駄なくキャッシュにできていないので、時間がかかってしまうのです。
そこで、組み合わせでははなく、もう一つシンプルな階乗の計算でキャッシュを作ることにしました。
(declaim (ftype (function (fixnum) fixnum)
fact))
(let ((cache (make-hash-table)))
(setf (gethash 0 cache) 1)
(defun fact (n)
(declare (type fixnum n))
(let ((resume (loop for i from n downto 0
until (gethash i cache)
finally (return i))))
(loop for i from (1+ resume) to n
do (setf (gethash i cache)
(mod-round (* i (gethash (1- i) cache))))
finally (return (gethash n cache))))))Code language: Lisp (lisp)このfact関数では、まずはもっとも大きなキャッシュを探して、そこから続きを計算していきます。
これを使えば、組み合わせ combiはすぐに計算できます。
(defun combi (n r)
(mod-round (* (fact n)
(mod-inv (fact (- n r)))
(mod-inv (fact r)))))
Code language: Lisp (lisp)これで、無事に時間以内に解決しました。
全体のコードは、
(defparameter *mod* (+ (expt 10 9) 7))
(defun mod-round (n)
(mod n *mod*))
(defun mod-pow (base exp)
(loop with result = 1
with b = (mod-round base)
with e = exp
while (> e 0)
do (when (oddp e)
(setf result (mod-round (* result b))))
(setf b (mod-round (* b b)))
(setf e (ash e -1))
finally (return result)))
(defun mod-inv (n)
(assert (/= (mod-round n) 0))
(mod-pow n (- *mod* 2)))
(declaim (ftype (function (fixnum) fixnum)
fact))
(let ((cache (make-hash-table)))
(setf (gethash 0 cache) 1)
(defun fact (n)
(declare (type fixnum n))
(let ((resume (loop for i from n downto 0
until (gethash i cache)
finally (return i))))
(loop for i from (1+ resume) to n
do (setf (gethash i cache)
(mod-round (* i (gethash (1- i) cache))))
finally (return (gethash n cache))))))
(defun combi (n r)
(mod-round (* (fact n)
(mod-inv (fact (- n r)))
(mod-inv (fact r)))))
;; x, y from 1 to W, H
(defun go-right-at-B-y (H W A B y)
(declare (type fixnum H W A B y))
(cond ((<= 1 y (- H A))
(mod-round (* (combi (+ (1- B) (1- y)) (1- y))
(combi (+ (- W B 1) (- H y)) (- H y)))))
(t 0)))
(defun pattern-not-go-under-A-B (H W A B)
(declare (type fixnum H W A B))
(loop for y from 1 to (- H A)
with result = 0 do
(setf result (mod-round
(+ result (go-right-at-b-y H W A B y))))
finally (return result)))
(defun solve ()
(let* ((H (read))
(W (read))
(A (read))
(B (read)))
(princ (pattern-not-go-under-a-b H W A B))))
#-swank
(solve)
Code language: Lisp (lisp)