40代文系社内SEがAtCoder Beginner Contest 143 D - Trianglesを解いてみた

様々な長さの棒が与えられ、その中から3本選んで三角形を作る選び方は何通りかを求める問題です。

まず注目したのは制約の10^3です。

あまり見かけない数字です。

N^2でも10^6なので2重ループが使えそうです。

3本の棒のうち、2本まで選ぶと3本目の長さの最大値が決まります。

棒の選び方にもともとの並び順は関係ないので、ソートしても問題ありません。

ということで2分探索が使えます。よっしゃ。

3本中2本を全探索で選び、残りの1本として選べる範囲を2分探索で求めることでACできました。

(defun solve ()
  (let* ((n (read))
         (l (make-array n :initial-contents (loop repeat n collect (read)))))
    (format t "~A~%" (solve2 l))))

(defun solve2 (l)
  (let* ((ll (make-array (1+ (length l)))))
    (loop for i from 0 below (length l) do (setf (aref ll i) (aref l i)))
    (setf (aref ll (1- (length ll))) (1+ (expt 10 3)))
    (sort ll #'<)
    (loop with ans = 0
          for i from 0 below (- (length ll) 2)
          do (loop for j from (1+ i) below (- (length ll) 1)
                   do (incf ans (solve1 ll i j)))
          finally
             (return ans))))

(defun solve1 (l i j)
  (labels ((f (min max)
             (if (= (1+ min) max)
                 min
                 (let* ((li (aref l i))
                        (lj (aref l j))
                        (mid (+ min (floor (- max min) 2)))
                        (lmid (aref l mid)))
                   (if (< lmid (+ li lj))
                       (f mid max)
                       (f min mid))))))
    (- (f j (1- (length l))) j)))

(solve)