Saruman's Army

quiz .hs

『プログラミングコンテストチャレンジブック』 から

N 個の点が直線上にあります。点 i の位置は Xi です。N 個のうちいくつかの点を選び、それらの点に印を付けます。N 個のすべての点について、距離が R 以内の場所に印を付けられた点がなければなりません(自分に印が付いていれば、距離が 0 のところにあると考えます)。条件を満たすようにしながら、できるだけ印を付ける点を少なくしたいです。何個の点に印を付ける必要があるでしょうか。


書籍と同じアルゴリズムで while ループを再帰に変えただけ。

import Data.List (sort)
import Test.HUnit

solve :: Int -> [Int] -> Int
solve r = length . mark [] 0 . sort
  -- (<=s+r) の地点のリストとそれ以降の地点のリストのペアについて考える
  -- (<=s+r) の地点のリストの末尾に印をつける
  -- p の地点に印をつけたら (<=p+r) の地点を除いて再び始めに戻って考える
  -- (<=s+r) の地点のリストが空の場合はそれ以降の地点の先頭を s にする
  where mark ps s xs = 
          case span (<=s+r) xs of
            ([], [])  -> ps
            ([], _)   -> mark ps (head xs) xs
            (ys, xs') -> let p = last ys
                         in  mark (p:ps) (p+r) (dropWhile (<=p+r) xs')

testSolve = runTestTT $ test [3 ~=? solve 10 [1, 7, 15, 20, 30, 50]]