【AtCoder, ABC086C】
Travelingとインデックスアク
セスのループ
（Common Lisp）

by
  • Common Lisp で AtCoder ABC086C を解いていたところ、時間制限を超えてしまいました。
  • 原因は nth によるリストのインデックスアクセスで、毎回先頭からたどるため全体の計算量が O(N²) になっていました。
  • loop for rest on を使ってポインタを順に送る方式に変えることで、計算量を O(N) に改善できました。

関連記事

1. 問題のおさらい

AtCoder Beginners Selection の ABC086C（Traveling）を Common Lisp で解いていたら、時間制限を超えてしまい、なかなかクリアできませんでした。

ABC086C（Traveling）は、2次元平面上の移動が実行可能かを判定する問題です1。
時刻 0 に (0,0) を出発し、N 個のチェックポイント (t_i, x_i, y_i) を順番に通過できるかを確かめます。

1.1. 最初のコード

隣接するチェックポイント間で移動できる条件は、そんなに複雑ではありません。

  • マンハッタン距離 dist が時間差 dt 以下であること、
  • そして dt - dist が偶数であること。

余った時間を往復運動で使いつぶすためです2。

(defun distance (pos1 pos2)
  (let ((x1 (first pos1))
        (y1 (second pos1))
        (x2 (first pos2))
        (y2 (second pos2)))
    (+ (abs (- x1 x2)) (abs (- y1 y2)))))

(defun movable-p (pos1 pos2 dt)
  (and (>= dt (distance pos1 pos2))
       (zerop (mod (- dt (distance pos1 pos2)) 2))))

(let* ((n (read))
       (time-points (append
                     '((0 0 0))
                     (loop for i from 1 to n
                           collect (list (read) (read) (read))))))
  (format t (if
             (loop for i from 1 to n
                   always (movable-p
                           (cdr (nth (- i 1) time-points))
                           (cdr (nth i time-points))
                           (- (car (nth i time-points))
                              (car (nth (- i 1) time-points)))))
             "Yes"
             "No")))Code language: Lisp (lisp)
1.1. 最初のコード

しかし、このコードには、2か所の問題点がありました。

  • メインループが nth でインデックスアクセスしていることです。
  • movable-p の中で distance を2回呼んでいることと、

2. nthは常に先頭からたどる

Common Lisp のリストはコンスセルを連結した片方向連結リストなので3、nth は先頭から順にたどるので時間がかかります4。

つまり、(nth i list) の計算量は O(i) で、ループ全体では O(N²) になります。
N が最大 10^5 なので、最悪 10^10 ステップに近い操作が行われ、時間がかかってしまいます。

加えて、(nth (- i 1) ...) と (nth i ...) はどちらも先頭から探し直しているのも非効率でした。
直前のステップで参照した要素を、毎回ゼロから追いかけ直しているわけですから。

2.1. loop for rest on list

そこで、loopでリストを順繰りに進んでいくようにしました。

loop for rest on list はリストの各コンスセルを rest に束縛しながら進みます5。

たとえば、(loop for x on '(a b c d)) を使うと、次の順で x を束縛します。

(a b c d)
(b c d)
(c d)
(d)Code language: Lisp (lisp)

毎回先頭からたどり直すのではなく、前回の続きのポインタをそのまま使うので、全体の計算量が O(N) になります。

(loop for rest on time-points
      while (cdr rest)
      always (let ((prev (car rest))
                   (now (cadr rest)))
               (movable-p
                (cdr prev)
                (cdr now)
                (- (car now) (car prev)))))Code language: Lisp (lisp)

while (cdr rest) を入れることで、末尾要素の単独処理を防いでいます6。
隣接する2要素は (car rest) と (cadr rest) で取りました。

3. distance の二重計算

もう一つの問題は、不要な再計算です。

movable-p では distance を2回呼んでいました。
and の短絡評価があるので最初の条件を通過しなければ2回目は呼ばれませんが7、条件を通過したときには同じ計算をもう一度やっています。

そこで、dist を let で一度だけ計算して束縛します8。

(defun movable-p (pos1 pos2 dt)
  (let ((dist (distance pos1 pos2)))
    (and (>= dt dist)
         (zerop (mod (- dt dist) 2)))))Code language: Lisp (lisp)

小さな計算なのでたいしたことないかな、と思ったのですが、扱うデータサイズが大きくなると、やはり無視できないみたいです。

4. 修正のまとめ

(defun distance (pos1 pos2)
  (let ((x1 (first pos1))
	(y1 (second pos1))
	(x2 (first pos2))
	(y2 (second pos2)))
    (+ (abs (- x1 x2)) (abs (- y1 y2))) ))

(defun movable-p (pos1 pos2 dt)
  (let ((dist (distance pos1 pos2)))
    (and (>= dt dist)
	 (zerop (mod (- dt dist) 2)))))

(let* ((n (read))
       (time-points (append
		     '((0 0 0))
		     (loop for i from 1 to n
			   collect (list (read) (read) (read))))))
  (format t (if
	     (loop for rest on time-points
		   while (cdr rest)
		   always (let ((prev (car rest))
				(now (cadr rest)))
			    (movable-p
			     (cdr prev)
			     (cdr now)
			     (- (car now) (car prev)))))
	     "Yes"
	     "No")))
4. 修正のまとめ
問題点原因修正
O(N²) のループnth による毎回の線形探索loop for rest on でポインタを送る
distance の二重計算and の条件式で2回呼び出しlet で結果を束縛してから再利用

連結リストをインデックスで扱うと、配列と同じ感覚で書いても計算量が跳ね上がります。
loop for i from 0 に慣れていると見落としやすいポイントで、リストをたどるときは on を使って構造に沿って動かすのが Common Lisp らしい書き方です。

  1. この問題は AtCoder Regular Contest 089 の A 問題として出題されたものが、AtCoder Beginners Selection にも収録されています。 – AtCoder Beginners Selection
  2. マンハッタン距離とは、2点間の水平・垂直方向の移動量の和で定義される距離です。座標 (x1, y1) と (x2, y2) のマンハッタン距離は |x1-x2| + |y1-y2| になります。直線距離（ユークリッド距離）とは異なり、格子状の移動しかできない場合に適した距離の測り方です。 – Manhattan distance – NIST
  3. コンスセルは car と cdr の2要素を持つメモリオブジェクトです。リストは複数のコンスセルを cdr でつないだ構造になっています。car が現在の要素を指し、cdr が次のコンスセルを指します。最後のセルの cdr は nil になります。 – cons – Wikipedia
  4. Common Lisp HyperSpec によると、nth は (car (nthcdr n list)) と定義されており、n 番目の要素に到達するまで先頭から cdr を n 回たどります。配列のようなランダムアクセスは行われません。 – CLHS: Accessor NTH
  5. for var on list 構文は、var をリストの連続するサブリスト（tail）に順番に束縛します。for var in list がリストの各要素を束縛するのに対し、on はコンスセルごとにポインタを進めます。 – Common Lisp the Language 2nd ed., §26.6 Iteration Control
  6. (cdr rest) が nil になるのはリストの末尾セルに達したときです。while (cdr rest) を省くと、末尾の要素だけが rest に残った状態でも always 節が実行され、存在しない (cadr rest) が nil になるためロジックが崩れます。
  7. Common Lisp の and は短絡評価を行い、左から順に評価して最初に nil を返したフォームの時点で評価を停止します。これは Ada の and then や Pascal の cand に相当する動作です。 – Common Lisp the Language 2nd ed., §6.4
  8. let は新しいレキシカルスコープを作り、指定した変数を並列に束縛します。let* は順番に束縛する点が異なり、後の束縛で前の変数を参照できます。どちらもローカル変数を導入する Common Lisp の基本フォームです。 – Common Lisp HyperSpec – Special Operator LET, LET*