【AtCoder ABC453C】
数直線上の通過回数
（bit全探索）

by
  • AtCoder ABC453Cは、数直線上を移動しながら原点を最大何回通過できるかを求める問題です。
  • 常に原点方向へ向かう貪欲法では最適解が得られないケースがあり、N≤20の制約を活かしたbit全探索が有効です。
  • 座標の掛け算によるオーバーフローと浮動小数点数の精度不足という2つのバグは、符号だけを取り出して掛け算する方法と、座標を2倍して整数のみで扱う方法でこれらを解消し、最終的にACを達成しました。

関連記事

1. 問題

数直線上の座標 0.50.5 に高橋君がいます。

高橋君はこれから NN 回の移動を行います。
ii 回目の移動では、「正の方向」「負の方向」のいずれかを選び、その方向に LiL_i 進みます。

高橋君は座標 00 を最大で何回通り過ぎることが出来るでしょうか？
なお、この問題の制約上、座標 00 で完了する移動が生じることはありません。

  • 1≤N≤201 \leq N \leq 20
  • 1≤Li≤1091 \leq L_i \leq 10^9
  • 入力はすべて整数
C – Sneaking Glances

2. 素朴な回答

とにかく現在地から原点方向に進むようにして、絶対値が入れ替わるタイミングをカウントしてみました。

問題：ABC453-C Sneaking Glances 座標 0.5 からスタート。N回移動して 座標0 を最大何回通れるか？ 制約：1 ≤ N ≤ 20　　1 ≤ Lᵢ ≤ 10⁹ 0 0.5 通過ポイント 各移動のルール ・正または負の方向を選ぶ ・選んだ方向に Lᵢ だけ進む ※座標0でぴったり止まることはない ゴール 座標0の通過回数を 最大化せよ 方向の選び方を工夫する 
(defun solve (x Ln)
  (loop for dx in Ln
	with pos = x
	with glance = 0
	do (when (> dx (abs pos))
	     (incf glance))
	   (if (> pos 0)
	       (decf pos dx)
	       (incf pos dx))
	finally (return glance)))Code language: Lisp (lisp)

ただし、正解 22、誤答 12。
どうも、考えに見落としがあるようです。

2. 素朴な回答
(defun solve (x Ln)
  (loop for dx in Ln
	with pos = x
	with glance = 0
	do (when (> dx (abs pos))
	     (incf glance))
	   (if (> pos 0)
	       (decf pos dx)
	       (incf pos dx))
	finally (return glance)))

(defun main ()
  (let* ((L (read))
	 (Ln (loop repeat L
		   collect (read))))
    (princ (solve 0.5 Ln))))

#-swank
(main)
Code language: Lisp (lisp)

3. 貪欲法の失敗例

なんとなく常に原点に向かえばよいわけではなさそうな気はしたのですが、具体的な失敗例が思い浮かびませんでした。
そこで、解説を読んでみました。

貪欲法の失敗例 L = (40, 50, 90, 1, 1, 1) 貪欲法（常に原点方向） 0 3回通過 VS 最適（負・負・正・…） 0 5回通過 教訓 最初に大きく遠ざかることで あとの通過回数が増える

座標が正なら負の方向に、負なら正の方向に移動するという貪欲法は失敗します。
例えば L=(40,50,90,1,1,1) の時、貪欲法に従うと座標 0 を 3 回通過することになりますが、最初に負・負・正の方向を選択することで座標 0 を 5 回通過することができます。

解説 – AtCoder Beginner Contest 453
(solve 0.5 '(40 50 90 1 1 1))
;=> 3   0.5 +> -39.5 +> 10.5 +> -79.5 -> -78.5 -> -77.5 -> -76.5 
;=> 5   0.5 +> -39.5 -> -89.5 +> 0.5 -> +0.5 +> 0.5 +> -0.5Code language: Lisp (lisp)

3.1. bit全探索

どんなパターンで最大になるのかがわかりません。
ここで、解説を読むと 制約 N <= 20 が大事なことがわかります。

N が小さいことを利用しましょう。

解説 – AtCoder Beginner Contest 453

つまり、2202^{20}なら総当りでも解決できそうなのです。

bit全探索 N ≤ 20　→　2²⁰ ≈ 100万通り　→　全探索可能 各移動の方向をbitで表現 0 1 0 1 1 … 負 正 負 正 正 0〜2ᴺ-1を列挙 （bit pattern） 各パターンで 通過回数をシミュレート 最大値を出力 → 正解34

そこでbit全探索ですべての場合を調べてみることにしました。

(defun solve (x Ln)
  (declare (type number x)
	   (type list Ln))
  (let* ((n (length Ln))
	 (vec (make-array n
			  :element-type 'fixnum
			  :initial-contents Ln)))
    (loop for bit from 0 below (ash 1 n)
	  maximize (glance-time x vec bit))))
Code language: Lisp (lisp)

00 〜 2n−12^n – 1 まで順番にチェックして、最大値を求めます。

(defun glance-time (x vec bit)
  (declare (type number x)
	   (type (simple-array fixnum (*)) vec)
	   (type fixnum bit))
  (loop for i below (length vec)
	with pos = x
	with prev = x
	with glance = 0
	do (incf pos (* (aref vec i)
			(if (logbitp i bit) 1 -1)))
	   (when (minusp (* prev pos))
	     (incf glance))
	   (setf prev pos)
	finally (return glance)))
Code language: Lisp (lisp)

そうしたところ、正解32、不正解2でした。

3.1. bit全探索

コードはこちら。

(defun solve (x Ln)
  (declare (type number x)
	   (type list Ln))
  (let* ((n (length Ln))
	 (vec (make-array n
			  :element-type 'fixnum
			  :initial-contents Ln)))
    (loop for bit from 0 below (ash 1 n)
	  maximize (glance-time x vec bit))))

(defun glance-time (x vec bit)
  (declare (type number x)
	   (type (simple-array fixnum (*)) vec)
	   (type fixnum bit))
  (loop for i below (length vec)
	with pos = x
	with prev = x
	with glance = 0
	do (incf pos (* (aref vec i)
			(if (logbitp i bit) 1 -1)))
	   (when (minusp (* prev pos))
	     (incf glance))
	   (setf prev pos)
	finally (return glance)))

(defun main ()
  (let* ((L (read))
	 (Ln (loop repeat L
		   collect (read))))
    (princ (solve 0.5 Ln))))

#-swank
(main)
Code language: Lisp (lisp)

4. 計算精度の問題

コードの中で怪しい部分は、2箇所あります。

計算精度の問題と解決 問題① オーバーフロー prev × pos で符号判定 → 大きな数で桁あふれ sign(prev)×sign(pos) で判定 問題② 浮動小数点誤差 初期位置 0.5 を float で保持 → 大きな数で精度が落ちる 座標を2倍 → 全て整数で処理 修正後 ✓ 符号のみ比較 ✓ 整数のみで演算 AC 正解 34 
(when (minusp (* prev pos))
      (incf glance))

(incf pos (* (aref vec i)
			(if (logbitp i bit) 1 -1)))Code language: Lisp (lisp)

１つ目は、原点を通り過ぎるタイミングの符号の違いを掛け算で求めていることです。
これは、prev, posが大きな数字になった場合にオーバーフローしてしまうことがあります。

0 を跨いだがどうか判定するには、移動前の座標を x 、移動後の座標を y として xy<0 かどうかで判定できます。そのまま判定するとオーバーフローのおそれがあるため、符号を保ったまま値を −1,0,1 のいずれかに圧縮してから判定するとよいです。

解説 – AtCoder Beginner Contest 453

そこで、事前に符号だけを求めてから掛け算します。

(defun sign (x)
  (cond ((plusp x) 1)
	((zerop x) 0)
	(t -1)))

 (when (minusp (* (sign prev) (sign pos)))
       (incf glance))Code language: Lisp (lisp)

２つ目は、posに数字を足していく部分です。
実は、初期位置が 0.5 だと浮動小数点数を使うことになります。
しかし、数値が大きくなると小数部分の精度が足りなくなってしまうことがあります。

シミュレートの際、 0.5 という数を扱うのは不便なので、座標・移動距離ともに 2 倍して考えると全てを整数で取り扱うことができて実装が楽です。

解説 – AtCoder Beginner Contest 453

この誤差を避けるには、浮動小数点数ではなく整数を使います。
そのため、Ln全体を 2 倍した vec-doubleを用意します。

(defun solve (Ln)
  (declare (type list Ln))
  (let* ((n (length Ln))
	 (vec-double (make-array n
				 :element-type 'fixnum)))
    (loop for L in Ln
		    for i from 0
		    do (setf (aref vec-double i) (* L 2)))
    (loop for bit from 0 below (ash 1 n)
	  maximize (glance-time vec-double bit))))
Code language: Lisp (lisp)

これでもglanceの回数は変わりません。

正解34。
無事に解決しました。

4. 計算精度の問題