【AtCoder ABC449D】
Make Target 2を考える
（Common Lisp）

by
  • AtCoderのABC449Dは、座標平面上でmax(|x|, |y|)が偶数になる格子点を数える問題です。
  • 二重ループによるO(n²)の解法は時間切れになるため、領域をy=±xで分割して計算量を減らす方法を考えました。
  • さらに第一象限に収まるシンプルなケースから出発し、象限をまたぐ場合を順に統合することでO(1)の解法に到達しました。
  • 最初に作った素朴な解法をテストの基準として使うことで、効率化したコードの正しさを確認しながら進められました。

関連記事

1. 素直に2重ループで解くと（9）

AtCoderのABC449D「Make Target 2」を考えました。
この問題は、X-Y平面上の条件に合う格子点の数を数える問題です。

2 次元座標平面があり、座標が (x, y) である格子点は max⁡(|x|,|y|)\max(|x|, |y|) が偶数のとき黒、奇数のとき白で塗られています。

L≤x≤RL \le x \le R かつ D≤y≤UD \le y \le U を満たす整数の組 (x, y) のうち、座標 (x, y) が黒く塗られているものの個数を求めてください。

  • −106≤L≤R≤106-10^6 \le L \le R \le 10^6
  • −106≤D≤U≤106-10^6 \le D \le U \le 10^6
  • 入力される値はすべて整数

入力は以下の形式で標準入力から与えられる。

L R D U
D – Make Target 2

まずは、x, y のループで黒かどうか判定する count-black-by-loopを作りました。

(defun blackp (x y)
  (evenp (max (abs x) (abs y))))

(defun count-black-by-loop (left right down up)
  (loop for x from left to right
        sum (loop for y from down to up
				 when (blackp x y)
				   count 1)))

(let ((left (read))
      (right (read))
      (down (read))
      (up (read)))
  (format t "~a" (count-black-by-loop left right down up)))Code language: JavaScript (javascript)

正解 9 時間切れ 20です。

1. 素直に2重ループで解くと（9）

やはり、O(n^2)だと、あっという間に時間切れになってしまいます。

1. 素直に2重ループで解くと（9）

1.1. 条件に合う点を図示してみる

どうも、部分的な範囲をまとめて計算する方法を考える必要があります。

そこで、条件を元に(x y）のリストを作り、GNUplotで図示してみました。

Gnuplot Produced by GNUPLOT 6.0 patchlevel 4 -20 -15 -10 -5 0 5 10 15 20 -20 -15 -10 -5 0 5 10 15 20 x y O “~/data1.txt” using 1:2

格子点が同心四角形上に並んでいます。

(defun blackp (x y)
  (evenp (max (abs x) (abs y))))

(defun make-points-2d (test-func-obj xmin xmax ymin ymax step)
  (loop for x from xmin to xmax by step
	append  (loop for y from ymin to ymax by step
		      when (apply test-func-obj (list x y))
			collect (list x y))))

(defun write-points (points filename)
  (with-open-file (out filename
                       :direction :output
                       :if-exists :supersede)
    (dolist (p points)
      (format out "~a ~a~%" (first p) (second p)))))

(write-points
 (make-points-2d
  (lambda (x y) (blackp x y))
  -20 20 -20 20 1)  "data1.txt")
Code language: JavaScript (javascript)

2. x, yの絶対値の大小で領域を分解すると

そこで、どうにかして計算で点の数を数えようと考えました。規則性をもとに上限と下限をから範囲内の点を計算できそうです。

しかし、散々、悩んだのですが、取っ掛かりがわからず、解説の冒頭を手がかりにすることにしました1。

max(∣x∣,∣y∣) という式を簡潔に扱うために、∣x∣>∣y∣ であるものと ∣x∣≤∣y∣ であるものに場合分けして数え上げ、最後に足し合わせることで答えを求めます。

確かに、y=xとy=-xの2直線で分割すると、すっきりします。
(A) abs x >= abs yの領域、
(B) abs x <= abs yの領域、
（C) abs x = abs yの領域 （A, Bの共通部分）
それぞれ規則的に点が並んでいます。

Gnuplot Produced by GNUPLOT 6.0 patchlevel 4 -20 -15 -10 -5 0 5 10 15 20 -20 -15 -10 -5 0 5 10 15 20 x y O “~/data2.txt” using 1:2 “~/data3.txt” using 1:2 “~/data4.txt” using 1:2

たとえば、(A) abs x >= abs yの領域だけに限ると、黒丸は規則的に増減します。
そこから、D〜Uの範囲に何個入るかを計算します。

(defun count-black-in-area-abs-x (L R D U)
  (loop for x from L to R
	when (evenp x)
	  sum (count-in-range x D U)))

(defun count-in-range (x D U)
  (max 0 (+ 1 (- (min U (abs x))
		 (max D (- (abs x)))))))Code language: JavaScript (javascript)

(B) abs x <= abs yの領域は、x, yを入れ替えれば、(A)とまったく同じ論法で計算できます。
最後に、（C)の部分が(A)と(B)で重複するので、引きます。

(defun count-black-in-area-abs-y (L R D U)
  (count-black-in-area-abs-x D U L R))

(defun count-black-in-line-abs-same (L R D U)
  (loop for x from L to R
	when (and (evenp x))
	  sum (cond
		((= x 0) (if (in-range x D U) 1 0))
		(t (+ (if (in-range x D U) 1 0)
		      (if (in-range (- x) D U) 1 0) )))))

(defun count-black-by-compute (L R D U)
  (- (+ (count-black-in-area-abs-x L R D U)
	(count-black-in-area-abs-y L R D U))
     (count-black-in-line-abs-same L R D U)))

(let ((left (read))
      (right (read))
      (down (read))
      (up (read)))
  (format t "~a" (count-black-by-compute left right down up)))
Code language: JavaScript (javascript)

2.1. テストパターンで検証する

いろんなパターンのパラメータを与えて、count-black-by-compute と count-black-by-loop を比較して、結果の正しさを確かめました。

(ql:quickload :parachute)
(parachute:define-test count-black-by-compute-test
  (parachute:is = (count-black-by-loop 0 3 1 3)
		(count-black-by-compute 0 3 1 3))
  (parachute:is = (count-black-by-loop -10 13 21 30)
		(count-black-by-compute -10 13 21 30))
  (parachute:is = (count-black-by-loop -30 -13 -21 -3)
		(count-black-by-compute -30 -13 -21 -3))
  (parachute:is = (count-black-by-loop -20 33 -11 3)
		(count-black-by-compute -20 33 -11 3)))

(parachute:test 'count-black-by-compute-test)

テストの途中で、count-black-in-line-abs-same の x = 0 のときは特別なことや、count-in-range は負の値になってはいけないことに気づきました。

2.2. まずはクリアした

二重ループを一重ループにすることができたので、制限時間内に解答することができました。

2.2. まずはクリアした

実行時間は、63msです。

3. さらに場合分けで計算する

この問題は、さらに計算効率を上げることができそうです。
コードを生成AIに見せたら、O(1)で解けるというのです。
悔しいので、答えは見ずに、あと一歩考えてみます。

確かに、たとえば、-16 <= x <= 12, 4 <= y <= 12 の範囲で見てみます。

Gnuplot Produced by GNUPLOT 6.0 patchlevel 4 -20 -15 -10 -5 0 5 10 15 20 -20 -15 -10 -5 0 5 10 15 20 x y O “~/data2.txt” using 1:2 “~/data3.txt” using 1:2 “~/data4.txt” using 1:2

すると、いくつかの等差数列に分解でき、必ずしも一行ずつカウントする必要がないことがわかります。

= 9 * 2 + (8+2) * 4 / 2 + (25 + 9) * 5 / 2 + (2 + 8) * 4 / 2

ただし、一般的な解法にするには、どのように分割するとよいのかを理解する必要があります。

3.1. 一番単純なケースを計算で求める

1日考えて、どうも良い分割の仕方が思いつかなかったので、解説の冒頭から手がかりを探すことにしました。
そこで、見つけたのは「部分問題」に分ける考え方。

L=D=0（かつ R,U≥0）を満たす部分問題について考えます。

iastmさんの解説 – AtCoder Beginner Contest 449

まず、もっとも単純な問題を計算し、それを利用して一般的な問題を解くことにしました。
L = D = 0 の場合で、R >= U のケースに注目します。
図示すると、このような形になります（R=20, U = 15）。

Gnuplot Produced by GNUPLOT 6.0 patchlevel 4 -20 -15 -10 -5 0 5 10 15 20 -20 -15 -10 -5 0 5 10 15 20 x y O “~/data1.txt” using 1:2

これが計算で求められれば、L > 0, D > 0 のときには、この部分集合を引いて、引きすぎた共通部分を足せばよいことになります。

（L > 0, D > 0） の場合、
S(L R D U)
= S(0 R 0 U) – S(0 L 0 U) – S(0 R 0 D) + S(0 L 0 D)
が成り立つ。

ということで、まずは原点から正のR, Lまでのシンプルな場合で数えます。
これは、同心四角形内と外を分けて足すことにしました。

(defun even-under (n)
  (- n (mod n 2)))

(defun count-in-concentric-quadrilaterals (n)
  (/ (* (+ 1 (* 2 (even-under n)) 1)
	(+ 1 (/ (even-under n) 2)))
     2))

(defun count-over-concentric-quadrilaterals (low high)
  (/ (* (1+ low)
	(- (even-under high) (even-under low)))
     2))

(defun count-black-in-first-quadrant-simple (R U)
    (cond
      ((> R U) (count-black-in-first-quadrant-simple U R))
      ((< R 0) 0)
      ( t (+ (count-in-concentric-quadrilaterals R)
	     (count-over-concentric-quadrilaterals R U)))))

この計算の場合分けは、結構ややこしくって。
区間の重複と奇数のケースで、何度もテストしました。

(progn 
  (ql:quickload :parachute)
  (parachute:define-test count-black-in-first-quadrant-simple-test
      (macrolet ((test-case (a b )
		   `(parachute:is
		     =
		     (count-black-by-loop 0 ,a 0 ,b)
		     (count-black-in-first-quadrant-simple ,a ,b))))
	(test-case 0 0 )
	(test-case 0 2 )
	(test-case 12 3)
	(test-case 1 4)
	(test-case 4 1)
	(test-case 4 0)
	))
  (parachute:test 'count-black-in-first-quadrant-simple-test))Code language: PHP (php)

3.2. 第一象限内に収まる場合を計算する

そうすると、第一象限に L R D Uが収まる場合は

;; assert 0 <= L <= R, 0 <= D
(defun count-black-in-first-quadrant (L R D U)
  (+ (- (count-black-in-first-quadrant-simple R U)
	(count-black-in-first-quadrant-simple (1- L) U)
	(count-black-in-first-quadrant-simple R (1- D)))
     (count-black-in-first-quadrant-simple (1- L) (1- D))))

ここでも、テストをしたり、シンプルな版の内訳を確認したりしながら、進めました。

(progn 
  (ql:quickload :parachute)
  (parachute:define-test count-black-in-first-quadrant-test
      (macrolet ((test-case (a b c d)
		   `(parachute:is
		     =
		     (count-black-by-loop ,a ,b ,c ,d)
		     (count-black-in-first-quadrant ,a ,b ,c ,d))))
	(test-case 0 0 0 0)
	(test-case 0 2 0 3)
	(test-case 0 12 0 3)
	(test-case 1 4 0 3)
	(test-case 0 4 1 3)
	(test-case 2 4 0 3)
	(test-case 0 4 2 3)
	(test-case 2 4 2 3)	  
	
	))
  (parachute:test 'count-black-in-first-quadrant-test))

(defun check-count-black-in-first-quadrant (L R D U)
  (list (count-black-in-first-quadrant-simple R U)
	(count-black-in-first-quadrant-simple (1- L) (1- U))
	(count-black-in-first-quadrant-simple (1- R) (1- D))
	(count-black-in-first-quadrant-simple (1- L) (1- D))
	(count-black-by-loop L R D U)
	))
Code language: PHP (php)

3.3. 2つ・4つの象限にまたがる場合を計算する

次は、まず第一象限・第二象限にまたがる場合を計算することにしました。
これが分かれば、そのほかのパターンも置き換えで計算できます。

この計算は、意外とかんたんで、Y軸を境界に分割してつなげるだけです。

;; asserts L <= 0 <= R, 0 <= D <= U
(defun count-black-in-two-quadrants (L R D U)
  (- 
   (+ (count-black-in-first-quadrant 0 R D U)
      (count-black-in-first-quadrant 0 (- L) D U))
   (count-black-in-first-quadrant 0 0 D U)))

Lが負なので、-Lにすれば第一象限に持ってきて計算できます。

残るは、4つの象限にまたがるパターン。
L R D U で設置する「窓」に原点が含まれる場合です。

(defun count-black-in-four-quadrants (L R D U)
  (- 
   (+ (count-black-in-two-quadrants L R 0    U)
      (count-black-in-two-quadrants L R 0 (- D)))
   (count-black-in-two-quadrants L R 0 0)))

これも、X軸で分割して下を反転すれば、それぞれ第一象限・第二象限にまたがるパターンに帰着します。

3.4. 入力値によって場合分け

ここまでで条件が決まれば計算できることがわかったので、最後はL R D Uの符号を確認して、場合分けしていきます。

厳しい条件から順に判定していきます。

(defun count-black-case-distiction (L R D U)
  (cond ((and (<= 0 L) (<= 0 D))
	 (count-black-in-first-quadrant L R D U))
	((and (<= 0 L) (< U 0))
	 (count-black-in-first-quadrant L R (- U) (- D)))
	((and (< R 0) (<= 0 D))
	 (count-black-in-first-quadrant (- R) (- L) D U))
	((and (< R 0) (< U 0)) 
	 (count-black-in-first-quadrant (- R) (- L) (- U) (- D)))
	((<= 0 D)
	 (count-black-in-two-quadrants L R D U))
	((> 0 U)
	 (count-black-in-two-quadrants L R (- U) (- D)))
	((<= 0 L)
	 (count-black-in-two-quadrants D U L R))
	((> 0 R)
	 (count-black-in-two-quadrants D U (- R) (- L)))
	(t (count-black-in-four-quadrants L R D U))))Code language: JavaScript (javascript)

場合分けが多いですが、意外とすんなりテストをクリアしました。

(progn 
  (ql:quickload :parachute)
  (parachute:define-test count-black-in-four-quadrants-test
      (macrolet ((test-case (a b c d)
		   `(parachute:is
		     =
		     (count-black-by-loop ,a ,b ,c ,d)
		     (count-black-in-four-quadrants ,a ,b ,c ,d))))
	(test-case -2 0 0 0)
	(test-case -5 2 -20 3)
	(test-case -3 12 0 3)
	(test-case -12 4 -5 3)
	(test-case -1 4 -1 3)
	(test-case -8 4 -10 3)
	(test-case -2 4 -2 3)
	(test-case -1 4 -2 3)))
  (parachute:test 'count-black-in-four-quadrants-test))Code language: PHP (php)

ということで、出来上がった答えは、

(defun even-under (n)
  (- n (mod n 2)))

(defun count-in-concentric-quadrilaterals (n)
  (/ (* (+ 1 (* 2 (even-under n)) 1)
	(+ 1 (/ (even-under n) 2)))
     2))

(defun count-over-concentric-quadrilaterals (low high)
  (/ (* (1+ low)
	(- (even-under high) (even-under low)))
     2))

(defun count-black-in-first-quadrant-simple (R U)
    (cond
      ((> R U) (count-black-in-first-quadrant-simple U R))
      ((< R 0) 0)
      ( t (+ (count-in-concentric-quadrilaterals R)
	     (count-over-concentric-quadrilaterals R U)))))

;; assert 0 <= L <= R, 0 <= D
(defun count-black-in-first-quadrant (L R D U)
  (+ (- (count-black-in-first-quadrant-simple R U)
	(count-black-in-first-quadrant-simple (1- L) U)
	(count-black-in-first-quadrant-simple R (1- D)))
     (count-black-in-first-quadrant-simple (1- L) (1- D))))

;; asserts L <= 0 <= R, 0 <= D <= U
(defun count-black-in-two-quadrants (L R D U)
  (- 
   (+ (count-black-in-first-quadrant 0 R D U)
      (count-black-in-first-quadrant 0 (- L) D U))
   (count-black-in-first-quadrant 0 0 D U)))

(defun count-black-in-four-quadrants (L R D U)
  (- 
   (+ (count-black-in-two-quadrants L R 0    U)
      (count-black-in-two-quadrants L R 0 (- D)))
   (count-black-in-two-quadrants L R 0 0)))

(defun count-black-case-distiction (L R D U)
  (cond ((and (<= 0 L) (<= 0 D))
	 (count-black-in-first-quadrant L R D U))
	((and (<= 0 L) (< U 0))
	 (count-black-in-first-quadrant L R (- U) (- D)))
	((and (< R 0) (<= 0 D))
	 (count-black-in-first-quadrant (- R) (- L) D U))
	((and (< R 0) (< U 0)) 
	 (count-black-in-first-quadrant (- R) (- L) (- U) (- D)))
	((<= 0 D)
	 (count-black-in-two-quadrants L R D U))
	((> 0 U)
	 (count-black-in-two-quadrants L R (- U) (- D)))
	((<= 0 L)
	 (count-black-in-two-quadrants D U L R))
	((> 0 R)
	 (count-black-in-two-quadrants D U (- R) (- L)))
	(t (count-black-in-four-quadrants L R D U))))

(let ((left (read))
      (right (read))
      (down (read))
      (up (read)))
  (format t "~a" (count-black-case-distiction left right down up)))
Code language: PHP (php)

コードは長くなりましたが、実行時間は 4ms。
大きなケースでも一瞬で解けるようになりました。

3.4. 入力値によって場合分け

4. 教訓：複雑な問題は分解する

今回の問題では、2つのことを学びました。

まず、第一は、複雑な問題はかんたんなパターンに分割して、答えを統合すること。

y = ± x で領域を分けたり、第一象限に収まるパターンだけを考えたり。
解きやすい問題に分割する視点が大事です。
とはいえ、わかっていても分割の視点に気づくのは大変で、自力では糸口を見つけられませんでした。

4.1. テストできる状況を作る

もう一つは、原始的な解き方もテストに役に立つこと。
はじめに作った回答は、本番では実行時間超過になってしまいましたが、多くのケースでは正しい答えを返します。

これを使うことで、効率化したバージョンに抜けや漏れがないかチェックできました。
そうすると、複雑な問題もテストでエラーになったケースを集中的に考えればよくなるので、解決まで早くなります。

  1. – 解説 – AtCoder Beginner Contest 449